AGC018D: Tree and Hamilton Path

https://agc018.contest.atcoder.jp/tasks/agc018_d

アイディア自体はそこまで難しくないけど、証明がややこしいやつ。

重心をとって、各子の部分木を渡り歩けば良いのかなぁという予想は簡単につくので、それが最善であることを頑張って示せばいいです。
ポイントは重心周りの辺全てを最善で取ることができないことと、ある部分木の大きさは他の部分木の大きさの合計以下になることです。

あとは重心が1つor2つの時を正しく捌けば大丈夫です。

int N;
vector<pl> G[MAX_N];
vi cen; //one or two
ll ans = 0;

int search_centroid(int v, int p) {
	int s = 1, m = 0;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i].fst;
		if(p == n) continue;
		int t = search_centroid(n, v);
		s += t;
		MAX(m, t);
	}
	MAX(m, N - s);
	if(m <= N / 2) {
		cen.pb(v);
	}
	return s;
}

int loop(int v, int p, ll c) {
	int tsize = 1;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i].fst;
		ll nc = G[v][i].sec;
		if(p == n) continue;
		tsize += loop(n, v, nc);
	}
	ans += tsize * c * 2;
	return tsize;
}

void solve() {
	cin >> N;
	rep(i, 0, N - 1) {
		int a, b; ll c;
		cin >> a >> b >> c; a--; b--;
		G[a].pb(pl(b, c));
		G[b].pb(pl(a, c));
	}
	search_centroid(0, -1);
	if(sz(cen) == 2) {
		int c1 = cen[0], c2 = cen[1];
		loop(c1, c2, 0);
		loop(c2, c1, 0);
		ll cost;
		rep(i, 0, sz(G[c1])) {
			if(G[c1][i].fst != c2) continue;
			cost = G[c1][i].sec;
		}
		ans += (N - 1) * cost;
	}
	else {
		int c = cen[0];
		loop(c, -1, 0);
		ll cost = inf;
		rep(i, 0, sz(G[c])) {
			MIN(cost, G[c][i].sec);
		}
		ans -= cost;
	}
	cout << ans << "\n";
}