http://codeforces.com/contest/827/problem/B
最初にrootを一つ決めて、あとはkコずつrootからまんべんなくつけていけば、木の高さが最小、かつその時の一番rootから離れているedgeの個数も最小になるのでこれが求めるグラフとなる。
int N, K; void solve() { cin >> N >> K; if((N - K - 1) % K == 0) cout << (N - K - 1) / K * 2 + 2 << "\n"; else if((N - K - 1) % K == 1) cout << (N - K - 1) / K * 2 + 3 << "\n"; else cout << (N - K - 1) / K * 2 + 4 << "\n"; vector<int> vec; rep(i, 0, K) vec.push_back(i + 1); int at = K + 1; while(at < N) { int a = vec[(at - 1) % K]; cout << a << " " << at << "\n"; vec[(at - 1) % K] = at; at++; } rep(i, 0, K) { cout << vec[i] << " " << N << "\n"; } }
こういうのをウニグラフというらしい。