#423 Div2 D
题意
构造一个 n 个节点的树，恰好有 k 个叶子节点 (叶子节点的定义是只与树上的某一个节点存在连边)，要求任意两个叶子节点的距离的最大值最小，距离为两个节点间边的数量，输出距离的最大值，以及 n - 1 条边。
分析
构造 “星型树” ，节点 1 为中心，首先连 k 条边到 k 个节点，对于多的点，周期性的绕最外层的 k 个点不断连接即可。
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
typedef pair<int, int> P;
vector<P> ans;
vector<int> v1, v2;
int main() {int n, k;cin >> n >> k;n--;n -= k;int lens = 2;for(int i = 2; i <= k + 1; i++) {ans.push_back(P(1, i));v1.push_back(i);}int z = k + 2;while(n) {lens++;if(n > 1) lens++;for(int i = 0; i < v1.size() && n > 0; i++) {ans.push_back(P(v1[i], z));v2.push_back(z);z++; n--;}v1.clear();v1 = v2;v2.clear();}cout << lens << endl;for(int i = 0; i < ans.size(); i++) {cout << ans[i].first << " " << ans[i].second << endl;}return 0;
}
