- [POI2008] STA-Station
114514
- 2025-5-28 16:31:51 @
#include<bits/stdc++.h>
#define int long long
using namespace std;
int f[1000005];
int sz[1000005];
vector<int>g[1000005];
int maxn,root;
int n;
void dfs(int u,int fa){
sz[u]=1;
for(int i:g[u]){
if(i!=fa){
dfs(i,u);
sz[u]+=sz[i];
f[u]+=f[i];
}
}
f[u]+=sz[u]-1;
return;
}
void findmax(int u,int fa){
for(int i:g[u]){
if(i!=fa){
f[i]=f[u]+n-2*sz[i];
findmax(i,u);
}
}
return;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
findmax(1,0);
for(int i=1;i<=n;i++){
if(maxn<f[i]){
maxn=f[i];
root=i;
}
}
cout<<root;
}
0 comments
No comments so far...
Information
- ID
- 398
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 7
- Tags
- # Submissions
- 26
- Accepted
- 9
- Uploaded By