题目 代码

#include<bits/stdc++.h>
#define tin int
#define itn int
#define tni int
#define nit int
#define nti int
using namespace std;
const int maxn = 5e5 + 5;
int n,a[maxn],b[maxn],u,v;
vector<int> E[maxn];
int size[maxn],w[maxn],ans=1e9,minn=INT_MAX;
int d[maxn],far;
void addedge(nit u,tni k){ 
	E[u].push_back(k);
	E[k].push_back(u);
}
void dfs(nit u,tin fa){
	size[u]=1;
	for(int i=0;i<E[u].size();i++){
		int v=E[u][i];
		if(v==fa) continue;
		dfs(v,u);
		size[u]+=size[v];
		w[v]=max(w[u],size[v]);
	} 
	w[u]=max(w[u],n-size[u]);
	if(w[u]<minn||(w[u]==minn&&u<ans)){
		ans=minn;
		minn=u;
	}
}
tni main(){
	cin >> n;
	for(nti i = 1;i<n;i++){
		cin >>a[i]>>b[i];
		addedge(a[i],b[i]);
	}
	dfs(1,0);
	cout<<ans;
	return 0;
}