https://www.luogu.com.cn/record/59439967

#include <iostream>
using namespace std;
const int kMaxN=1e6+1;
struct EDGE
{
  int to,nt;
}e[kMaxN*2];
int cnt,hd[kMaxN];
int n;
int size[kMaxN],dp[kMaxN],deep[kMaxN];
int maxdp,ans;
void Add(int a,int b)
{
  e[++cnt].to=b;
  e[cnt].nt=hd[a];
  hd[a]=cnt;
}
void dfs(int now,int last)
{
  deep[now]=deep[last]+1;
  dp[1]+=deep[now];
  size[now]=1;
  for(int i=hd[now];i;i=e[i].nt)
  {
    if(e[i].to==last)continue;
    dfs(e[i].to,now);
    size[now]+=size[e[i].to];
  }
}
void Count(int now,int last)
{
  if(now!=1)
  {
    dp[now]=dp[last]-size[now]+n-size[now];
    if(dp[now]>maxdp)
    {
      maxdp=dp[now];
      ans=now;
    }
  }
  for(int i=hd[now];i;i=e[i].nt)
  {
    if(e[i].to==last)continue;
    Count(e[i].to,now);
  }
}
int main()
{
cin>>n;
for(int i=1;i<n;i++)
{
  int a,b;
  cin>>a>>b;
  Add(a,b);
  Add(b,a);
}
dfs(1,0);
maxdp=dp[1],ans=1;
Count(1,0);
cout<<ans;
return 0;
}