#include<bits/stdc++.h>
using namespace std;
struct edge {
int to,nxt;
} e[1000010<<1];
int n,cnt,id;
int head[1000010];
long long ans;
long long f[1000010],dep[1000010],size[1000010];
inline void add(int u,int v){
e[++cnt].nxt=head[u];
head[u]=cnt;
e[cnt].to=v;
}
void dfs1(int x,int fa){
size[x]=1;
dep[x]=dep[fa]+1;
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==fa)continue;
dfs1(y,x);
size[x]+=size[y];
}
}
void dfs2(int x,int fa){
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==fa)continue;
f[y]=f[x]+n-2*size[y];
dfs2(y,x);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
dfs1(1,0);
for(int i=1;i<=n;i++)f[1]+=dep[i];
dfs2(1,0);
for(int i=1;i<=n;i++)if(ans<f[i])ans=f[i],id=i;
printf("%d",id);
return 0;
}
标签:std,1000010,struct,nxt,题解,P3478
From: https://www.cnblogs.com/zan-mei-tai-yang/p/18498074