对于节点 $u$ 而言，他的儿子就是 $v$。我们定义 $sz_u$ 表示以节点 $u$ 为根的子树的节点数量。那么可以得到 $sz_u = 1 + \sum sz_v$，显然需要一次 $\texttt{DFS}$ 来计算所有的 $sz_i$，这次的 $\texttt{DFS}$ 就是预处理。

考虑 $\texttt{dp}$，换根 $\texttt{dp}$，顾名思义，就是要换根，那么就可以考虑从 $f_u \to f_v$，但在转移时，节点的深度会发生改变。

• 所有是 $v$ 的子树，节点深度都会减少 $1$，那么总和就减少 $sz_v$。
• 所有不是 $v$ 的子树，节点深度都会增加 $1$，那么总和就加上 $n-sz_v$。

综上所述，我们就可以得到状态转移方程为：

#include <iostream>
#include <vector>
#define int long long
using namespace std;
const int N = 1e6 + 5; 
vector<int> g[N];
int sz[N], f[N], dep[N], n;
inline void dfs(int u, int fa)
{
	sz[u] = 1;//记录大小 
	dep[u] = dep[fa] + 1;//记录深度 
	for(int i = 0; i < g[u].size(); i++){
		int v = g[u][i];
		if(v == fa) continue;
		dfs(v, u);//往下深搜 
		sz[u] += sz[v];//加上儿子的大小 
}
inline void dp(int u, int fa)
{
	for(int i = 0; i < g[u].size(); i++){
		int v = g[u][i];
		if(v == fa) continue;
		f[v] = f[u] - sz[v] * 2 + n;//dp 
		dp(v, u);//继续往下dp 
	}
}
signed main()
{
	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, 1);
	for(int i = 1; i <= n; i++) f[1] += dep[i];
	dp(1, 1);
	int ans = -1;
	int id;
	for(int i = 1; i <= n; i++){//统计答案 
		if(f[i] > ans){//如果大于ans，就记录 
			ans = f[i];
			id = i;//编号 
		}
	}
	cout << id;//输出 
	return 0;//华丽结束 
}