70分求助
查看原帖
70分求助
195705
李湛然楼主2021/3/7 16:18
#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e6+5;
long long n;
long long head[N];
long long nxt[N];
long long v[N];
long long tot=0;
long long dp[N];
long long Size[N];
long long dep[N];
void add(long long x,long long y)
{
	tot++;
	nxt[tot]=head[x];
	head[x]=tot;
	v[tot]=y;
	return ;
}
void dfs(long long x,long long fa)
{
	Size[x]=1;
	dep[x]=dep[fa]+1;
	for(long long i=head[x];i;i=nxt[i])
	{
		if(v[i]!=fa)
		{
			dfs(v[i],x); 
			Size[x]+=Size[v[i]];
		}
	}
	return ;
}
void dfs_dp(long long x,long long fa)
{
		for(long long i=head[x];i;i=nxt[i])
		{
			dp[x]=dp[fa]-Size[x]+n-Size[x];
			if(v[i]!=fa)
				dfs_dp(v[i],x);
		}
}
int main()
{
	cin>>n;
		long long u,v;
	for(long long i=1;i<n;i++)
	{
		cin>>u>>v;
		add(u,v);
		add(v,u); 
	}
	dfs(1,1);
	for(long long i=2;i<=n;i++)
	{
		dp[1]+=(dep[i]-1);
	}
	dfs_dp(1,1);
	long long Max=-1;
	long long Maxi;
	for(long long i=1;i<=n;i++)
	{
	//	cout<<Size[i]<<" "; 
	//	cout<<i<<" "<<dp[i]<<" ";
		if(dp[i]>Max)
		{
			Max=dp[i];
			Maxi=i;
		}
		//cout<<endl;
	}
	cout<<Maxi;
	return 0;
}
2021/3/7 16:18
加载中...