普通树形 DP 常问“根固定为 1 时，某个子树的答案是什么”；换根 DP 再追问一步：如果把根从父节点移到相邻孩子，哪些贡献改变了？在树上删掉这条边后，全部顶点只分成孩子侧与其余侧，所以重新计算通常可以压缩成一次加、一次减。

本文用三题建立一条递进路线：先处理可以写成总和的距离代价，再识别 Tree Painting 隐藏的深度和，最后处理不能用单个全局总量概括、需要传递“父侧最优贡献”的最大连通子图。

1. 官方资料与学习目标

题目 官方评分 官方标签 约束 本文核心
1092F Tree with Maximum Cost 1900 dfs and similar、dp、trees n≤2×10^5，a_i≤2×10^5 加权距离和的换根公式
1187E Tree Painting 2100 dfs and similar、dp、trees n≤2×10^5 把游戏得分改写成深度和
1324F Maximum White Subtree 1800 dfs and similar、dp、graphs、trees n≤2×10^5 从子树最优扩展到父侧最优

三题都能在线性时间内完成。真正需要掌握的不是“写两遍 DFS”，而是下面这条推导链：

代码全部使用父节点数组与遍历序列，避免在 n=2×10^5 的链上递归过深。

2. 换根为什么只需要看一条边

先以 1 为根，考虑父节点 u 与孩子 v。删掉边 u-v 后：

  • v 的原子树在一侧；
  • 剩余所有点在另一侧；
  • 从根 u 移到 v 时，第一侧的距离全部减 1，第二侧的距离全部加 1。

因此，只要自底向上预先算出 v 这一侧的总量，就不必为每个新根重新遍历整棵树。

3. 第一题：1092F Tree with Maximum Cost

3.1 目标与朴素方法

每个点 i 有正权 a_i。选择根 r 后，代价为：

$$F(r)=\sum_i a_i\cdot dist(i,r).$$

需要输出最大的 F(r)。如果对每个根分别 BFS/DFS，复杂度是 O(n^2)，链形树在最大规模下无法运行。

3.2 固定根时要保存什么

先以 1 为根，定义：

  • sub[v]：v 原子树内的权值总和；
  • total：全树权值总和；
  • F(1)：遍历时把 depth[v] * a[v] 累加。

自底向上有：

$$sub[u]=a_u+\sum_{v\text{ 是 }u\text{ 的孩子}}sub[v].$$

3.3 换根公式

根从 u 移到孩子 v：

  • v 子树内权值共 sub[v]，距离各减 1，贡献减少 sub[v]；
  • 子树外权值共 total-sub[v]，距离各加 1，贡献增加 total-sub[v]。

所以：

$$F(v)=F(u)-sub[v]+(total-sub[v])=F(u)+total-2sub[v].$$

部分 权值和 距离变化 对答案的改变量
v 子树 sub[v] -1 -sub[v]
其余顶点 total-sub[v] +1 +total-sub[v]

3.4 手工演算

链 1-2-3-4 的权值为 [2,1,3,2]，以 1 为根：

根 加权距离和
1 0×2+1×1+2×3+3×2=13
2 13+8-2×6=9
3 9+8-2×5=7
4 7+8-2×2=11

最大值是 13。这里 sub[2]=6、sub[3]=5、sub[4]=2，每一步都只用上一个根的答案。

3.5 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<long long> weight(n);
    long long total = 0;
    for (long long& value : weight) {
        cin >> value;
        total += value;
    }

    vector<vector<int>> graph(n);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    vector<int> parent(n, -2), depth(n, 0), order;
    parent[0] = -1;
    order.push_back(0);
    for (int i = 0; i < n; ++i) {
        const int vertex = order[i];
        for (int next : graph[vertex]) {
            if (next == parent[vertex]) continue;
            parent[next] = vertex;
            depth[next] = depth[vertex] + 1;
            order.push_back(next);
        }
    }

    vector<long long> subtree = weight;
    long long rootCost = 0;
    for (int vertex = 0; vertex < n; ++vertex) {
        rootCost += weight[vertex] * depth[vertex];
    }
    for (int i = n - 1; i > 0; --i) {
        const int vertex = order[i];
        subtree[parent[vertex]] += subtree[vertex];
    }

    vector<long long> cost(n, 0);
    cost[0] = rootCost;
    long long answer = rootCost;
    for (int i = 1; i < n; ++i) {
        const int vertex = order[i];
        cost[vertex] = cost[parent[vertex]] + total - 2 * subtree[vertex];
        answer = max(answer, cost[vertex]);
    }
    cout << answer << '\n';
    return 0;
}

时间 O(n)，空间 O(n)。最大答案可能达到约 8×10^15，必须使用 long long。

4. 第二题：1187E Tree Painting

4.1 先把游戏翻译成静态量

开始时全白。第一次任选一个点涂黑，之后每次只能选与黑点相邻的白点；得分是被选点所在白色连通块的大小。

选定第一个点 r 后，把树看成以 r 为根：一个点只有在父节点已经黑色后才能被选到，而它的后代此时仍是白色。因此选点 v 时，白色连通块恰好是 v 的子树，得分为 size[v]。

总分为：

$$S(r)=\sum_v size_r[v].$$

每个点 x 会被自己及所有祖先的子树各统计一次，共 depth_r[x]+1 次，所以又有：

$$S(r)=\sum_x(depth_r[x]+1)=n+\sum_x depth_r[x].$$

原来的操作顺序消失了，问题变成“选择一个根，使所有点深度和最大”。

4.2 换根公式

这次每个点权值都是 1。若初始根为 1，先算 size[v] 与：

$$S(1)=n+\sum_v depth[v].$$

根从 u 移到孩子 v 时，v 子树的 size[v] 个点深度减 1，其余 n-size[v] 个点深度加 1：

$$S(v)=S(u)+n-2size[v].$$

这正是上一题公式令所有 a_i=1 后的形式，只多了对所有根相同的常数 n。

4.3 手工演算

树边为 1-2、1-3、2-4、2-5，以 1 为根：

项目 值
深度 [0,1,1,2,2]
S(1) 5+(0+1+1+2+2)=11
size[2] 3
S(2) 11+5-2×3=10
size[3] 1
S(3) 11+5-2×1=14

点 3 看似是叶子，却能让大多数点离根更远，因此取得更高总分。

4.4 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<vector<int>> graph(n);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    vector<int> parent(n, -2), depth(n, 0), order;
    parent[0] = -1;
    order.push_back(0);
    for (int i = 0; i < n; ++i) {
        const int vertex = order[i];
        for (int next : graph[vertex]) {
            if (next == parent[vertex]) continue;
            parent[next] = vertex;
            depth[next] = depth[vertex] + 1;
            order.push_back(next);
        }
    }

    vector<int> size(n, 1);
    long long rootScore = n;
    for (int value : depth) rootScore += value;
    for (int i = n - 1; i > 0; --i) {
        const int vertex = order[i];
        size[parent[vertex]] += size[vertex];
    }

    vector<long long> score(n, 0);
    score[0] = rootScore;
    long long answer = rootScore;
    for (int i = 1; i < n; ++i) {
        const int vertex = order[i];
        score[vertex] = score[parent[vertex]] + n - 2LL * size[vertex];
        answer = max(answer, score[vertex]);
    }
    cout << answer << '\n';
    return 0;
}

时间 O(n)，空间 O(n)。

5. 第三题：1324F Maximum White Subtree

5.1 把颜色变成权值

白点记为 +1，黑点记为 -1。对每个点 v，要求一个包含 v 的连通子图，使点权和最大。

固定根 1，先定义：

$$down[u]=w_u+\sum_{v\text{ 是孩子}}\max(0,down[v]).$$

如果某个孩子方向的最优贡献为负，就不接入；为正才值得保留。down[u] 只看得到原子树，还不是最终答案。

5.2 父侧怎样传给孩子

假设已经知道 answer[u]，要转移到孩子 v：

  1. answer[u] 中可能包含 v 方向的正贡献，先减掉 max(0,down[v])；
  2. 得到从 u 通往树外其余部分的贡献 outside；
  3. 对 v 来说，只有 outside>0 才值得接入。

于是：

$$outside=answer[u]-\max(0,down[v]),$$

$$answer[v]=down[v]+\max(0,outside).$$

5.3 手工演算

链 1-2-3-4 颜色为黑、白、白、黑，对应 [-1,+1,+1,-1]，以 1 为根：

点 down 解释
4 -1 只有黑点自己
3 1 不接负贡献的点 4
2 2 接入点 3
1 1 自己 -1，加上点 2 方向的 2

向下换根后，点 3 可以从父侧接入点 2 的正贡献，所以 answer[3]=2；点 4 也可接入点 2、3，得到 1。最终答案 [1,2,2,1]。

5.4 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> weight(n);
    for (int& value : weight) {
        cin >> value;
        value = value == 1 ? 1 : -1;
    }

    vector<vector<int>> graph(n);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    vector<int> parent(n, -2), order;
    parent[0] = -1;
    order.push_back(0);
    for (int i = 0; i < n; ++i) {
        const int vertex = order[i];
        for (int next : graph[vertex]) {
            if (next == parent[vertex]) continue;
            parent[next] = vertex;
            order.push_back(next);
        }
    }

    vector<int> down = weight;
    for (int i = n - 1; i > 0; --i) {
        const int vertex = order[i];
        down[parent[vertex]] += max(0, down[vertex]);
    }

    vector<int> answer(n, 0);
    answer[0] = down[0];
    for (int i = 1; i < n; ++i) {
        const int vertex = order[i];
        const int outside = answer[parent[vertex]] - max(0, down[vertex]);
        answer[vertex] = down[vertex] + max(0, outside);
    }

    for (int value : answer) cout << value << ' ';
    cout << '\n';
    return 0;
}

时间 O(n)，空间 O(n)。

6. 三题的换根状态有什么区别

题目 第一遍统计 第二遍传递 能否只靠一个全局总量
1092F 子树权值和、根 1 的加权距离和 +total-2×sub[v] 可以
1187E 子树大小、根 1 的深度和 +n-2×size[v] 可以
1324F 子树内包含当前点的最大贡献 去掉孩子贡献后传父侧正贡献 不可以

前两题的目标对所有点贡献做线性求和，切边后只需知道两侧的“量”；第三题带有“负贡献可以不选”的最优化决策，必须保留方向性状态。

7. 正确性证明

7.1 1092F

固定边 u-v 且 u 是 v 的父亲。换根到 v 后，v 原子树内每个点距离恰减 1，其余点距离恰加 1。按权值求和得到 F(v)=F(u)+total-2sub[v]。根 1 的值直接计算正确；沿父子边传播覆盖所有点，故每个根的值正确，取最大即为答案。

7.2 1187E

选定首个黑点后，树的唯一简单路径保证任何点被选前其父亲必须已黑，而其未选后代仍构成白色连通块，所以该步得分等于当前根下的子树大小。所有子树大小之和等于每点的祖先数之和，即 n+深度和。换根的深度变化与 1092F 全部点权为 1 时相同，因此公式与最大值均正确。

7.3 1324F

对固定根，包含 u 且限于其子树的最优连通块，在每个孩子方向可以独立决定接入或舍弃；接入的最优收益为 down[v]，只有为正时有利，因此 down 转移正确。计算孩子 v 时，从 answer[u] 移除其中可能采用的 v 方向，剩余就是父侧可提供的最优连通贡献；同样只在为正时接入。树上各方向被恰好考虑一次，故 answer[v] 是包含 v 的全树最优值。

8. 边界与错误清单

  1. 把换根写成每个根重新 DFS。 复杂度会退化到 O(n^2)。
  2. 1092F 用 int。 权值、距离与求和相乘后必须用 long long。
  3. 换根时只减子树，不加外部。 一条边的两侧距离变化方向相反。
  4. Tree Painting 直接搜索涂色顺序。 顺序不是状态；固定首点后总分已经由根树确定。
  5. 误写 S(r)=深度和。 每个点还会被自己的子树统计一次，需要加 n。
  6. 1324F 强行接入负贡献。 每个方向都应取 max(0, contribution)。
  7. 计算父侧时不移除孩子贡献。 会把 v 方向重复计入。
  8. 递归 DFS 直接跑 20 万点长链。 C++ 默认栈可能溢出，迭代遍历更稳妥。
  9. 父节点数组只判断 next != parent，却没有建立树。 应保证每个点只从父亲首次进入；树输入下本文写法成立。
  10. 忘记单点与全黑情况。 1092F 单点答案为 0；1324F 全黑时每点答案为 -1。

9. 独立验证

tests/verify-rerooting-three-article.cjs 会提取并无警告编译三份 C++17 代码，并采用不同思路核验：

  • 1092F 对小树枚举每个根，用 BFS 直接求所有距离与加权和；
  • 1187E 对每个候选首点直接计算 n+深度和；
  • 1324F 枚举所有点集，检查连通性，并为每个必含点寻找最大权值和；
  • 三题另用 20 万点长链检查迭代遍历、64 位上界与线性复杂度。

10. 下一步

可以先回看树上 DFS 三题，确认深度、路径和子树贡献的基本语义；再读本文理解根移动时怎样复用答案。之后可进入树的直径、最近公共祖先或树链剖分：它们同样利用唯一简单路径，但维护的信息不再只沿一条父子边更新。