本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-08-31 23:19:36

做法

dfs 每个点作为根，计算答案。

dfs 时，设当前点是 $u$，转移到其子节点 $v$ 时，考虑一下答案变化：

以 $v$ 为根节点的子树所有节点深度减一。

所有不在 $v$ 的子树的节点深度加一。

所以预处理每个节点子树的大小，然后 dfs 转移就行。

Code

#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
int n;
int head[maxn];
struct EDGE
{
	int to,nxt;
}edge[maxn<<1];
int cnt;
inline void add(int u,int to)
{
	edge[++cnt].to=to;
	edge[cnt].nxt=head[u];
	head[u]=cnt;
}
int size[maxn];
void dfs(int u,int _fa)
{
	size[u]++;
	for(int i=head[u];i;i=edge[i].nxt)
	{
		int to=edge[i].to;
		if(to==_fa)continue;
		dfs(to,u);
		size[u]+=size[to];
	}
}
ll f[maxn];
void redfs(int u,int _fa)
{
	for(int i=head[u];i;i=edge[i].nxt)
	{
		int to=edge[i].to;
		if(to==_fa)continue;
		f[to]=f[u]+ll(n-2*size[to]);
		redfs(to,u);
	}
}
int main()
{
	scanf("%d",&n);
	int u,v;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++)
	{
		f[1]+=(ll)size[i];
	}
	redfs(1,0);
	ll ans=0;
	int out=1;
	for(int i=1;i<=n;i++)
	{
		if(f[i]>ans)
		{
			ans=f[i];
			out=i;
		}
	}
	printf("%d",out);
	return 0;
}