80qt WA
查看原帖
80qt WA
745667
xiepingfang楼主2023/10/4 16:34

rt

#include <bits/stdc++.h>
using namespace std;
int head[2000001], big[2000001], deap[2000001], dp[2000001], cnt;
struct node{
    int next, to;
}e[2000001];
void add(int x, int y){
    e[++cnt].to=y;
    e[cnt].next=head[x];
    head[x]=cnt;
}
void serch1(int x, int from){
    big[x]=1;
    for (int i=head[x]; i; i=e[i].next){
        int y=e[i].to;
        if (y==from){
            continue;
        }
        deap[x]=deap[from]+1;
        serch1(y, x);
        big[x]+=big[y];
    }
}
void serch2(int x, int from){
    for (int i=head[x]; i; i=e[i].next){
        int y=e[i].to;
        if (y==from){
            continue;
        }
        dp[y]=dp[x]-2*big[y]+big[1];
        serch2(y, x);
    }
}
int main(){
    int n;
    cin >> n;
    for (int i=1; i<=n; i++){
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }
    serch1(1, 0);
    for (int i=1; i<=n; i++){
        dp[1]+=deap[i];
    }
    serch2(1, 0);
    int sum=0, id;
    for (int i=1; i<=n; i++){
        if (sum<dp[i]){
            sum=dp[i];
            id=i;
        }
    }
    cout << id;

    return 0;
}
2023/10/4 16:34
加载中...