一、定义
在一棵无根树中，若需要分别计算以多个节点为根的多个答案，而当节点总数 \(n\) 过大时，则可以考虑使用 二次扫描与换根法 。
二、解法
解决方法如下：换根 dp 通常会与树形 dp 结合，我们可以先任定一个根节点 \(root\) ，通过树形 dp 的思想计算出一个答案，再考虑当 \(root\) 的子节点作为根节点时，答案怎样变化。一般可以在 \(O(1)\) 的复杂度内完成答案的转化。这样整道题的复杂度就由 \(O(n ^ 2)\) 降为了 \(O(n)\)
在代码中，我们一共需要两个 \(dfs\) 函数，第一个处理以 \(root\) 为根时的答案，第二个进行换根操作。具体见例题。
三、例题
1、Sta
分析：
此题非常经典和模板。我们可以先求解出以节点 1 为根节点时的答案，再考虑换根。
见下图：
显然，当 1 的儿子节点 3 成为根时，红圈中所有节点的深度都会减 1，而其它节点的深度都会加 1。推广一下即得：设以 \(i\) 为根时的答案为 \(dp_i\) ，其子树（包括自己）的节点一共有 \(size_i\) 个 ，若有两个节点 \(u\) 和 \(v\)，\(v\) 是 \(u\) 的儿子节点，则有： \(dp_v = dp_u - size_v + (n - size_v)\) ，这样我们就以 \(O(1)\) 的时间复杂度得到了以另一个节点为根时的答案。
Code:
#include<bits/stdc++.h>
using namespace std;
#define SF scanf
#define PF printf
#define int long long
struct Edge {
int to, next;
}edge[2000005];
int head[1000005], cnt, dep[1000005], siz[1000005], dp[1000005], n;
void add(int u, int v) {
edge[++cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt;
}
void dfs1(int x, int fa) {
dep[x] = dep[fa] + 1;
siz[x] = 1;
for(int i = head[x]; i; i = edge[i].next) {
int to = edge[i].to;
if(to == fa) continue;
dfs1(to, x);
siz[x] += siz[to];
}
}
void dfs2(int x, int fa) {
for(int i = head[x]; i; i = edge[i].next) {
int to = edge[i].to;
if(to == fa) continue;
dp[to] = dp[x] - siz[to] + (n - siz[to]);
dfs2(to, x);
}
}
signed main() {
SF("%lld", &n);
for(int i = 1; i < n; i++) {
int u, v;
SF("%lld%lld", &u, &v);
add(u, v), add(v, u);
}
dfs1(1, 0);
for(int i = 1; i <= n; i++) dp[1] += dep[i];
dfs2(1, 0);
int ans = 0, index;
for(int i = 1; i <= n; i++) {
if(dp[i] > ans) ans = dp[i], index = i;
}
PF("%lld", index);
return 0;
}
2、积蓄程度
分析：
我们先考虑一个节点最多能蓄的水受哪些因素影响。
首先，若它的所有儿子最多只能蓄 \(a\) 的水，那它蓄的水一定不能超过 \(a\) ，不然无法满足儿子的条件。其次，如果它的父亲到它间的河道只能蓄 \(b\) 的水，那它最多只能得到 \(b\) 的水。所以，它最多能蓄的水就是 \(\min(a, b)\) 。不过为了换根方便，我们可以把 \(a\) 和 \(\min(a, b)\) 都存下来。
现在思考如何换根。
令 \(dp_i\) 为以 \(i\) 为根时的答案， \(sum_i\) 为 \(i\) 节点的所有儿子最多蓄的水。若有两个节点 \(u\) 和 \(v\) ， \(v\) 是 \(u\) 的儿子节点，他们之间的河道能蓄 \(w\) 的水。因为现在 \(u\) 是根节点，自身能得到无限多的水，易证 \(dp_u = sum_u\)， 换根后显然 \(v\) 就变成了 \(u\) 的父亲节点。此时 \(u\) 的儿子最多能蓄的水就变成了 \(dp_u - sum_v\)，而 \(u\) 节点最多也只能得到 \(w\) 的水了。因此 \(u\) 对 \(v\) 的贡献即为 \(\min(dp_u - sum_v, w)\)，再加上 \(v\) 原来儿子能蓄的水，即得到了 \(dp_v\) 。
方程式可写作： \(dp_v = sum_v + \min(dp_u - sum_v, w)\)。
但有一种特殊情况：如果 \(u\) 节点只能到达 \(v\) 这一个节点，那么换根后 \(u\) 节点一定是叶子节点，可以排无限多的水。贡献即为它最多能得到的水 \(w\) 。 写作： \(dp_v = sum_v + w\)
Code:
#include<bits/stdc++.h>
using namespace std;
#define SF scanf
#define PF printf
#define int long long
struct Edge {
int to, next, w;
}edge[400005];
int head[200005], cnt, dp[2][200005], n, ans[200005], d[200005];
// 0 儿子最多能装的 1 自己最多能装的
void add(int u, int v, int w) {
edge[++cnt].to = v;
edge[cnt].next = head[u];
edge[cnt].w = w;
head[u] = cnt;
}
void dfs1(int x, int fa, int Max) {
bool flag = true;
for(int i = head[x]; i; i = edge[i].next) {
int to = edge[i].to;
if(to == fa) continue;
flag = false;
dfs1(to, x, edge[i].w);
dp[0][x] += dp[1][to];
}
dp[1][x] = min(Max, dp[0][x]);
if(flag) dp[1][x] = Max;
}
void dfs2(int x, int fa) {
for(int i = head[x]; i; i = edge[i].next) {
int to = edge[i].to;
if(to == fa) continue;
if(d[x] == 1) ans[to] = dp[0][to] + edge[i].w;
else ans[to] = dp[0][to] + min(ans[x] - dp[1][to], edge[i].w);
dfs2(to, x);
}
}
signed main() {
int t;
SF("%lld", &t);
while(t--) {
cnt = 0;
memset(head, 0, sizeof(head));
memset(dp, 0, sizeof(dp));
SF("%lld", &n);
for(int i = 1; i < n; i++) {
int u, v, w;
SF("%lld%lld%lld", &u, &v, &w);
d[u]++, d[v]++;
add(u, v, w), add(v, u, w);
}
dfs1(1, 0, 1e18);
ans[1] = dp[1][1];
dfs2(1, 0);
int sum = 0;
for(int i = 1; i <= n; i++) sum = max(sum, ans[i]);
PF("%lld\n", sum);
}
return 0;
}