#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