不是题解,或许吧

换根dp版题

#include<iostream>
#include<queue>
#include<list>
int n,max=0,maxi;
long long sum[1000001],ans[1000001];//sum记录子树大小;ans记录以i为根的树的总深度
std::list<int>map[1000001];//map存图(在使用命名空间std时不要这么写)
void dfs(int x=1,int pa=0,int d=0){//dfs计算以x为根的子树大小以及以1为根的树的总深度
    ans[1] = d,sum[x] = 1;
    for(int i:map[x]){
        if(i==pa)continue;
        dfs(i,x,d+1);
        sum[x] += sum[i];
    }
}
void dfs2(int x=1,int pa=0){//dfs2计算最大值以及ans[x]
    if(pa)ans[x] = ans[pa] + n - 2*sum[x];//换根dp递推
    if(ans[x]>max)max = ans[x],maxi = x;//统计最大值,以及达到最大值时的索引
    for(int i:map[x])if(i!=pa)dfs2(i,x);
}
int main(){
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0);
    std::cin >> n;
    for(int i(1),u,v;i<n;++i)std::cin >> u >> v,map[u].push_back(v),map[v].push_back(u);
    dfs();
    dfs2();
    std::cout << maxi;
    return 0;
}