树形动态规划与换根 DP (Tree DP & Rerooting)¶

树形动态规划是将动态规划的状态定义在树形拓扑结构上的算法范式。树天然具备“子树无环”、“递归自相似”以及“割断任意边即分成两棵独立子树”的优良性质，使得状态转移具有清晰的拓扑依赖。

1. 基础树形 DP：自底向上的子树汇聚¶

在基础树形 DP 中，通常以节点 \(u\) 为局部子树的根，利用后序深度优先搜索（Post-order DFS）先递归求解所有子节点 \(v\) 的状态，再将子树信息汇总转移至父节点 \(u\)。

1.1 树上最大独立集 (以打家劫舍 III 为例)¶

要求在树中选择若干不相邻节点，使得点权和最大。

状态设计：对每个节点 \(u\)，定义二元状态：
\(dp[u][0]\)：不选取节点 \(u\) 时，子树 \(u\) 的最大点权和；
\(dp[u][1]\)：选取节点 \(u\) 时，子树 \(u\) 的最大点权和。
状态转移方程：
若选 \(u\)，则其所有直属子节点 \(v\) 均绝对不可选取：\(dp[u][1] = val[u] + \sum_{v \in son(u)} dp[v][0]\)；
若不选 \(u\)，则子节点 \(v\) 可选可不选（取收益较大者）：\(dp[u][0] = \sum_{v \in son(u)} \max(dp[v][0], dp[v][1])\)。

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

#include <utility>
#include <algorithm>

// 返回 pair<int, int>: first 为不选当前节点，second 为选当前节点
std::pair<int, int> dfs_rob(TreeNode* root) {
    if (!root) return {0, 0};

    auto left = dfs_rob(root->left);
    auto right = dfs_rob(root->right);

    // 1. 选当前根节点
    int rob_cur = root->val + left.first + right.first;
    // 2. 不选当前根节点
    int not_rob = std::max(left.first, left.second) + std::max(right.first, right.second);

    return {not_rob, rob_cur};
}

2. 树上最长路径与树的直径 DP¶

在树上求解两点间的最长简单路径（树的直径）是树形 DP 的经典模型：

最高转折点视角：对于任意节点 \(u\)，穿过 \(u\) 且以 \(u\) 为最高转折点（即两端点 LCA）的最长简单路径，等于 \(u\) 向下延伸到叶子的最长链加上次长链（来自不同子树分支）；
自底向上转移：在 DFS 回溯遍历子节点 \(v\) 时：
维护子节点向下延伸的最大深度 \(d_1[u]\) 和次大深度 \(d_2[u]\)；
动态用 \(d_1[u] + d_2[u]\) 更新全局直径最大值；
向上返回当前子树能为父节点提供的单侧最长贡献 \(d_1[u] + w\)；
点权与带约束变种：树形 DP 相比两次 BFS 最大的优势在于天然支持负权边、负点权以及属性约束（如 LC 124 二叉树中的最大路径和与 LC 2246 相邻字符不同的最长路径）。

[!TIP] 树的直径完整的数学定义、两次 BFS 算法与严格反证法证明、树的中心与最小高度树、两树合并定理及 7 道精选真题，请参阅专门专题： 👉 树的直径 (Tree Diameter) 核心算法与严格证明。

3. 换根 DP (All-Pairs Rerooting DP / 两次 DFS 范式)¶

3.1 核心痛点与换根突破¶

许多问题要求求解以树中每个节点分别作为整棵树的根时，对应的全局统计指标（如树中距离之和、最远可达距离等）。

若对每个节点分别运行一次 DFS，总时间复杂度为 \(\mathcal{O}(N^2)\)，当 \(N \ge 10^5\) 时必然超时；
换根 DP 通过两次 DFS，在严格 \(\mathcal{O}(N)\) 时间内求出全部 \(N\) 个节点作为根的答案！

3.2 换根算法两步法 (以 LeetCode 834 树中距离之和为例)¶

第一次 DFS (自底向上计算子树局部量)¶

选取任意节点（如节点 \(0\)）为临时根，后序遍历整棵树：

计算以 \(u\) 为根的子树节点总数 \(sz[u] = 1 + \sum sz[v]\)；
计算子树内所有节点到 \(u\) 的距离和：\(dp[u] = \sum (dp[v] + sz[v])\)。

第二次 DFS (自顶向下换根转移)¶

当根从父节点 \(u\) 移动到其直属子节点 \(v\) 时（相当于边 \((u, v)\) 的上下角色对调）：

靠近效应：以 \(v\) 为根的子树内部的全部 \(sz[v]\) 个节点，到新根的距离均缩短了 \(1\)（贡献 \(-sz[v]\)）；
远离效应：除 \(v\) 之外的全树其他所有节点（共有 \(N - sz[v]\) 个），到新根的距离均增加了 \(1\)（贡献 \(+(N - sz[v])\)）；
换根状态转移方程：

\[ ans[v] = ans[u] - sz[v] + (N - sz[v]) \]

#include <vector>

class Solution {
    std::vector<std::vector<int>> g;
    std::vector<int> sz, ans;
    int n;

    // DFS 1: 自底向上求以 0 为根时，子树内部的距离和与大小
    void dfs1(int u, int p) {
        sz[u] = 1;
        for (int v : g[u]) {
            if (v == p) continue;
            dfs1(v, u);
            sz[u] += sz[v];
            ans[u] += ans[v] + sz[v];
        }
    }

    // DFS 2: 自顶向下换根转移，O(1) 计算子节点为全局根的答案
    void dfs2(int u, int p) {
        for (int v : g[u]) {
            if (v == p) continue;
            // 换根公式
            ans[v] = ans[u] - sz[v] + (n - sz[v]);
            dfs2(v, u);
        }
    }

public:
    std::vector<int> sumOfDistancesInTree(int n, std::vector<std::vector<int>>& edges) {
        this->n = n;
        g.assign(n, {});
        sz.assign(n, 0);
        ans.assign(n, 0);

        for (const auto& e : edges) {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }

        dfs1(0, -1);
        dfs2(0, -1);
        return ans;
    }
};

时间复杂度：\(\mathcal{O}(N)\)，两次 DFS 遍历树中所有边。
空间复杂度：\(\mathcal{O}(N)\)，递归栈与邻接表。

4. 树上状态机与最小支配集 (LeetCode 968)¶

在二叉树上安装摄像头，每个摄像头可以监控自身、父节点及两个子节点，求监控全树所需的最小摄像头数。

贪心状态设计 (三种完备状态)¶

对每个节点定义三种相互排斥的充要状态：

状态 0 (未被覆盖)：当前节点尚未被任何摄像头覆盖，迫切需要其父节点安装摄像头来拯救；
状态 1 (放置了摄像头)：当前节点安装了摄像头；
状态 2 (已被覆盖)：当前节点已被子节点的摄像头覆盖，自身未装摄像头，也不需要父节点特别照顾。

后序贪心转移逻辑¶

若左右子节点存在任意一个为状态 0（未覆盖）：当前节点必须安装摄像头（变为状态 1），摄像头计数 \(+1\)；
若左右子节点均已被覆盖且无未覆盖者，但至少有一个子节点装了摄像头（状态 1）：当前节点已被覆盖（变为状态 2）；
若左右子节点均自身为状态 2（已被更下层覆盖）：当前节点暂时未被覆盖（变为状态 0），将安装责任向上推迟给父节点，实现最大化贪心覆盖！

5. LeetCode 经典真题精选与题解提示¶

LeetCode 337 - 打家劫舍 III (House Robber III) 中等
提示

树上最大独立集基准题。
- 每个节点维护包含当前节点（选）与不包含当前节点（不选）的最大点权和。
- 选当前点则子节点必不选；不选当前点则子节点可选可不选取较大者。
LeetCode 124 - 二叉树中的最大路径和 (Binary Tree Maximum Path Sum) 困难
提示

子树单侧链与全局路径汇聚。
- 递归函数返回以当前节点为顶端、向左或向右子树延伸的单侧最大正增益路径（负收益则截断为 0）。
- 在当前节点将左子树单侧最大链、右子树单侧最大链与自身节点值拼接，动态挑战全局最大路径和。
LeetCode 834 - 树中距离之和 (Sum of Distances in Tree) 困难
提示

换根 DP 标杆神题。
- DFS 1 后序遍历计算子树规模与局部距离和；
- DFS 2 前序遍历实现换根推导：\(ans[v] = ans[u] - sz[v] + (n - sz[v])\)。
LeetCode 968 - 监控二叉树 (Binary Tree Cameras) 困难
提示

树上最小支配集状态机。
- 划分“未覆盖、安装摄像头、已被覆盖”三种完备状态。
- 叶子节点绝不安摄像头（贪心推迟给其父节点）；DFS 根节点若最终返回未覆盖状态，需额外在根节点补装一个摄像头。
LeetCode 2603 - 收集所有金币的最少步数 (Collect Coins in a Tree) 困难
提示

树上拓扑剥皮剪枝 + 树形思维。
- 无金币的叶子节点永远不需要访问，先通过类似拓扑排序剥除所有无金币分支；
- 既然能在距离金币为 2 的节点收集，再将所有含金币的叶子节点向内连续剥离 2 层；
- 剩余的核心树结构中，每条保留的边必须恰好经过两次（一去一回），答案即为剩余边数 \(\times 2\)。