思路：首先先求出以1为根的答案，然后考虑由i转移到i的儿子的答案的变化，显然以son[i]为根的子树的所有结点的深度都会减一，其余的点的深度都会加一，然后就可以直接O(n)求出所有结点的答案，然后取max更新答案即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn 1000005 int n,tot;
int now[maxn],pre[*maxn],son[*maxn],dep[maxn],size[maxn];
long long dp[maxn]; int read(){
int x=;char ch=getchar();
for (;ch<''||ch>'';ch=getchar());
for (;ch>=''&&ch<='';ch=getchar()) x=x*+ch-'';
return x;
} void add(int a,int b){
son[++tot]=b;
pre[tot]=now[a];
now[a]=tot;
} void link(int a,int b){
add(a,b),add(b,a);
} void dfs(int x,int fa){
dep[x]=dep[fa]+,dp[x]=dep[x],size[x]=;
for (int p=now[x];p;p=pre[p])
if (son[p]!=fa){
dfs(son[p],x);
dp[x]+=dp[son[p]];
size[x]+=size[son[p]];
}
} void tree_dp(int x,int fa){
for (int p=now[x];p;p=pre[p])
if (son[p]!=fa){
dp[son[p]]=dp[x]+n-*size[son[p]];
tree_dp(son[p],x);
}
} int main(){
n=read();
for (int i=,a,b;i<n;i++) a=read(),b=read(),link(a,b);
dfs(,),tree_dp(,);int ans=;
for (int i=;i<=n;i++) if (dp[ans]<dp[i]) ans=i;
printf("%d\n",ans);
return ;
}