换根 dp，又叫二次扫描，属于树形 dp 的范畴。一般具有一下几个特点：
- 当指定的根节点不同时，题目求解的答案不同。
- 在转移期间需要不止一个节点的信息。
- 需两次 dfs，第一次为预处理，第二次为 dp 过程。
预处理
本题需要记录每个节点的两个信息：
- 节点 \(u\) 的深度 \(d_u\)。
- 当树根为 \(1\) 时，以节点 \(u\) 为根的子树的节点数 \(\mathit{sz}_u\)。易得 \(\mathit{sz}_u = 1 + \sum_{v \in \operatorname{son}(u)} \mathit{sz}_v\)。
换根 dp
令 \(f_u\) 为以 \(u\) 为根时所有节点的深度之和。\(\forall v \in \operatorname{son}(u)\)，将原来的「以 \(u\) 为根」转移到「以 \(v\) 为根」。
考虑原来是 \(v\) 以及 \(v\) 的后代的节点，它们的深度将减少 \(1\)。而其他节点的深度会增加 \(1\)。故得转移方程：
\[f_v = f_u - \mathit{sz}_v + n - \mathit{sz}_v
\]
参考代码
#include <bits/stdc++.h>
#define int long long
using namespace std;constexpr int N = 1e6 + 10;
int n, u, v, d[N], sz[N], f[N];
vector<int> tr[N];// 初始化
void init(int u, int fa = 0) {d[u] = u == 1 ? 0 : d[fa] + 1;sz[u] = 1;for (int i : tr[u])if (i != fa) {init(i, u);sz[u] += sz[i];}
}// 换根 dp
void dp(int u, int fa = 0) {for (int i : tr[u])if (i != fa) {f[i] = f[u] - sz[i] + n - sz[i];dp(i, u);}
}signed main() {ios::sync_with_stdio(0);cin.tie(nullptr), cout.tie(nullptr);cin >> n;for (int i = 1; i < n; i++) {cin >> u >> v;tr[u].emplace_back(v);tr[v].emplace_back(u);}init(1);f[1] = accumulate(d + 1, d + n + 1, 0ll);dp(1);cout << max_element(f + 1, f + n + 1) - f;
}
