G5 - 连通无环无向图的重心

struct { int to, ptr; } ar[maxn << 1u];
int head[maxn + 1];
int cnt[maxn + 1];
int papa[maxn + 1];

void dfs(int u, int fa) {
	cnt[u] = 1, papa[u] = fa;
	for (int i = head[u]; i; i = ar[i].ptr)
		if (ar[i].to != fa) {
			dfs(ar[i].to, u);
			cnt[u] += cnt[ar[i].to];
		}
}

int main() {
	ios::sync_with_stdio(false);

	int n;
	cin >> n;
	for (int i = 1; i < n; i++) {
		static int from, to, idx = 1;
		cin >> from >> to;
		ar[idx] = {to, head[from]};
		head[from] = idx++;
		swap(from, to);
		ar[idx] = {to, head[from]};
		head[from] = idx++;
	}
	dfs(1, 0);
	cnt[0] = cnt[1];
	int ret = n, ans = 0;
	for (int k = 1; k <= n; k++) {
		static int res;
		res = cnt[1] - cnt[k];
		for (int i = head[k]; i; i = ar[i].ptr)
			if (ar[i].to != papa[k]) res = max(res, cnt[ar[i].to]);
		if (res < ret) ret = res, ans = k;
	}
	printf("%d\n", ans);

	return 0;
}