知予牌超级无敌巨详细题解

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
#define ll long long
vector<ll>g[maxn];
ll fa[maxn],deep[maxn];//fa表示父亲  deep表示从1开始的深度
ll sum[maxn]; //以u作为根的子树大小
ll mx = 0;  //到所有点的距离的最大值
int flag = 1;
//第一次求值，以1作为根，求解每一个点的子树大小和深度，统计以1为根的距离和
void getsum(int from){
    sum[from] = 1;//自己本身就是一个点，计入子树大小
    mx += deep[from];//将所有点的距离和加在一起
    for(auto &to : g[from]){//遍历所有点
        if(to == fa[from]){//走到了父亲的位置
            continue;
        }
        fa[to] = from;//记录父亲
        deep[to] = deep[from] + 1;//子节点深度 = 父亲深度+1
        getsum(to);//递归计算子树
        sum[from] += sum[to]; //根的包含节点数量 = 所有孩子的数量
    }
}
void dfs(int from, ll ans){//以from作为根，距离和 
    if(ans > mx){//如果存在一个更大的
        mx = ans;//更新值
        flag = from;//更新点
    }
    else if(ans == mx){
        flag = min(flag,from);
    }
    for(auto &to : g[from]){
        if(to == fa[from]){
            continue;
        }
        //换根dp
        dfs(to,ans + (sum[1] - sum[to] - sum[to]));
    }
}
int main(){
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        int x;
        int y;
        cin >> x;
        cin >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    getsum(1);//以1作为根，sum[] deep[]
    dfs(1,mx);// 原先根据1构建的树，现在换根  依据1作为原有数据
    cout << flag << endl;
    return 0;
}