正经题解
2025-07-10 10:03:17
发布于:浙江
13阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
const int M=2000005;
int n,h[N],to[M],ne[M],p[N],d[N],s[N],Q[N];
long long f[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++) h[i]=-1;
int u,v,e=0;
for(int i=1;i<n;i++){
cin>>u>>v;
ne[e]=h[u]; to[e]=v; h[u]=e++;
ne[e]=h[v]; to[e]=u; h[v]=e++;
}
int l=0,r=0;
Q[r++]=1; p[1]=0; d[1]=0;
while(l<r){
int x=Q[l++];
for(int i=h[x]; i!=-1; i=ne[i]){
int y=to[i];
if(y==p[x]) continue;
p[y]=x;
d[y]=d[x]+1;
Q[r++]=y;
}
}
long long S=0;
for(int i=0;i<n;i++) S += d[Q[i]];
for(int i=1;i<=n;i++) s[i]=1;
for(int i=n-1;i>0;i--){
int x = Q[i];
s[p[x]] += s[x];
}
f[1] = S;
long long b = S;
int a = 1;
for(int i=1;i<n;i++){
int x=Q[i];
int pr=p[x];
f[x] = f[pr] + (long long)(n - 2*s[x]);
if(f[x] > b){
b = f[x];
a = x;
}
}
cout<<a;
return 0;
}
全部评论 1
顶
2025-07-10 来自 浙江
0
有帮助,赞一个