CF AIM Tech Round4C: Upgrading Tree

http://codeforces.com/contest/843/problem/C

重心を根としてウニみたいなグラフを構成します。具体的な方法は
http://kmjp.hatenablog.jp/entry/2017/09/05/0900
ここに書いてあります。
重心が複数個あるときもほとんど同じです。(複数といっても高々2つなんですが。2つの時は頂点数N/2の木2つを根でくっつけたものになります。)

こういうpathの長さに関するグラフ構築問題はウニグラフを作れると信じてやるのがよさそうですね。
実際過去に解いた問題に同じようなやつがありました。
Codeforces Round #423B: High Load - omochan's diary

すべてのpathの長さの総和みたいなのを求めるのは結構大変だし(マージテクでO(NlogN)かな?)、変な形のグラフが答えになると、judgeも正解か判定するのが困難になって出題できなくなると思います。

int N;
vector<int> G[MAX_N];
int S[MAX_N];
bool cen[MAX_N];
vector<int> C;
vector<int> sub[MAX_N], pre[MAX_N];
vector<vi> ans;

int dfs(int v, int p) {
	int cnt = 1;
	bool ok = true;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i];
		if(n == p) continue;
		int a = dfs(n, v);
		if(a > N / 2) ok = false;
		cnt += a;
	}
	if(N - cnt > N / 2) ok = false;
	if(ok) {
		C.pb(v);
		cen[v] = true;
	}
	return cnt;
}

void dfs2(int v, int p, int c) {
	if(v != c && p != c) {
		sub[c].pb(v);
		pre[c].pb(p);
	}
	rep(i, 0, sz(G[v])) {
		int n = G[v][i];
		if(p == n) continue;
		dfs2(n, v, c);
	}
}

void solve() {
	cin >> N;
	rep(i, 0, N - 1) {
		int a, b; cin >> a >> b; a--; b--;
		G[a].pb(b);
		G[b].pb(a);
	}
	dfs(0, -1);
	// debug(C);
	rep(i, 0, sz(C)) {
		int v = C[i];
		rep(j, 0, sz(G[v])) {
			int n = G[v][j];
			if(cen[n]) continue;
			dfs2(n, v, n);

			int k = sz(sub[n]);
			if(k == 0) continue;
			ans.pb({v, n, sub[n][0]});
			rep(j, 0, k - 1) {
				int a = sub[n][j], b = pre[n][j], c = sub[n][j + 1];
				ans.pb({a, b, n});
				ans.pb({v, a, c});
			}
			int a = sub[n][k - 1], b = pre[n][k - 1];
			ans.pb({a, b, n});
			ans.pb({v, a, n});
		}
	}
	cout << sz(ans) << "\n";
	rep(i, 0, sz(ans)) {
		cout << ans[i][0] + 1 << " " << ans[i][1] + 1 << " " << ans[i][2] + 1 << "\n";
	}
}

それにしてもjudgeに時間がかかりすぎだろ。(5分くらい?)