题解

两个深搜，注释可以看看

#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
const int N=1e6+5;
vector<int>e[N];
ll n,dep[N],siz[N],ans;//dep代表深度之和
void read(){//读边
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
}
ll dfs1(int x,int fa,int deep){//第一次DFS，取得以1为根情况下的深度之和
    ll num=deep;
    //还需要记录子树的大小
    siz[x]=1;
    for(auto i:e[x]){
        if(i!=fa){
            num=dfs1(i,x,deep+1);//记录深度之和
            siz[x]+=siz[i];//记录子树大小
        }
    }
    return num;
}
void dfs2(int x,int fa){
    for(auto i:e[x]){
        if(i!=fa){
            dep[i]=dep[x]+(siz[1]-siz[i])-siz[i];
            //当前为根深度和=之前点为根深度和+下降子树大小+上升子树大小
            dfs2(i,x);
        }
    }
}
int main(){
    cin>>n;
    read();
    dep[1]=dfs1(1,0,0);
    dfs2(1,0);
    for(int i=1;i<=n;i++)//扫描一遍dep，得到最大时的下标
        if(dep[ans]<dep[i])
            ans=i;
    cout<<ans;
    return 0;
}