树形动态规划（Tree DP）深度解析：从原理到实战（C++实现）

树形动态规划是解决树形结构最优化问题的强大工具，通过递归遍历树结构，在节点上定义状态并合并子树信息来求解全局最优解。本文将系统讲解树形DP的核心思想、基础模型、高级技巧及C++实现，涵盖20+经典问题解析。

树形DP本质：在树的后序遍历过程中，通过"子问题->父问题"的状态转移完成动态规划

一、树形DP基础概念

1.1 树形DP的核心思想

• 树形结构：利用树的天然递归特性
• 自底向上：通过后序遍历实现状态转移
• 状态定义：dp[u][state]表示以u为根的子树在特定状态下的最优解
• 状态转移：dp[u] = F(dp[v1], dp[v2], ..., dp[vk])，其中v是u的子节点

1.2 树形DP的适用场景

1. 树形结构问题：节点间存在父子关系
2. 子树独立：子问题之间互不影响
3. 最优子结构：父问题解可由子问题解推导
4. 无后效性：当前状态仅与子状态有关

1.3 树形DP的解题步骤

1. 建图（邻接表存储树）
2. 设计状态（关键步骤）
3. 状态转移方程
4. 初始化边界（叶子节点）
5. 递归求解（DFS后序遍历）
6. 获取结果（根节点状态）

二、树形DP的通用框架

2.1 树结构存储

const int N = 1e5 + 5;
vector<int> tree[N]; // 邻接表

void buildTree() {
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
}

2.2 递归框架模板

int dp[N]; // 一维状态示例

void dfs(int u, int parent) {
    // 初始化边界（叶子节点）
    
    for (int v : tree[u]) {
        if (v == parent) continue; // 避免回父节点
        
        dfs(v, u); // 递归遍历子树
        
        // 状态转移：用子节点v更新父节点u
        dp[u] = merge(dp[u], dp[v]); 
    }
    
    // 可选：后处理
}

2.3 多状态设计模板

int dp[N][2]; // 二维状态：0/1表示不同状态

void dfs(int u, int parent) {
    // 初始化
    dp[u][0] = 0;
    dp[u][1] = value[u];
    
    for (int v : tree[u]) {
        if (v == parent) continue;
        
        dfs(v, u);
        
        // 状态转移
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
}

三、经典问题模型与C++实现

3.1 最大独立集（没有上司的舞会）

问题：选择不相邻节点使权值和最大

状态设计：

• dp[u][0]：不选节点u的最大权值
• dp[u][1]：选择节点u的最大权值

状态转移：

void dfs(int u, int parent) {
    dp[u][0] = 0;
    dp[u][1] = happy[u]; // happy[u]为节点权值
    
    for (int v : tree[u]) {
        if (v == parent) continue;
        
        dfs(v, u);
        
        dp[u][0] += max(dp[v][0], dp[v][1]); // u不选，v可选可不选
        dp[u][1] += dp[v][0]; // u选，v必不选
    }
}

3.2 树的最小点覆盖

问题：选择最少的点覆盖所有边

状态设计：

• dp[u][0]：不选u时覆盖子树的最小点数
• dp[u][1]：选择u时覆盖子树的最小点数

状态转移：

void dfs(int u, int parent) {
    dp[u][0] = 0;
    dp[u][1] = 1;
    
    for (int v : tree[u]) {
        if (v == parent) continue;
        
        dfs(v, u);
        
        dp[u][0] += dp[v][1]; // u不选，v必选
        dp[u][1] += min(dp[v][0], dp[v][1]); // u选，v可选可不选
    }
}

3.3 树的最小支配集

问题：选择最少的点使每个点要么被选要么相邻点被选

状态设计：

• dp[u][0]：u被选中
• dp[u][1]：u未被选中，但被父节点覆盖
• dp[u][2]：u未被选中，但被子节点覆盖

状态转移：

void dfs(int u, int parent) {
    dp[u][0] = 1;
    dp[u][1] = 0;
    dp[u][2] = 0;
    
    bool has_child_cover = false;
    int min_diff = INT_MAX;
    
    for (int v : tree[u]) {
        if (v == parent) continue;
        
        dfs(v, u);
        
        dp[u][0] += min({dp[v][0], dp[v][1], dp[v][2]});
        dp[u][1] += min(dp[v][0], dp[v][2]);
        
        if (dp[v][0] <= dp[v][2]) {
            has_child_cover = true;
            dp[u][2] += dp[v][0];
        } else {
            dp[u][2] += dp[v][2];
            min_diff = min(min_diff, dp[v][0] - dp[v][2]);
        }
    }
    
    if (!has_child_cover) 
        dp[u][2] += min_diff; // 强制选择一个子节点
}

四、树形DP进阶模型

4.1 树上背包（树形依赖背包）

问题：选子节点必须选父节点，求最大价值

状态设计：
dp[u][j]：以u为根的子树，容量为j的最大价值

状态转移：

void dfs(int u, int parent) {
    // 初始化：必选当前节点
    for (int j = weight[u]; j <= m; j++) 
        dp[u][j] = value[u];
    
    for (int v : tree[u]) {
        if (v == parent) continue;
        
        dfs(v, u);
        
        // 背包转移（倒序枚举容量）
        for (int j = m; j >= weight[u]; j--) {
            // 枚举分配给子树的容量
            for (int k = 0; k <= j - weight[u]; k++) {
                dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k]);
            }
        }
    }
}

4.2 树的直径（最长路径）

问题：求树上最长路径长度

状态设计：

• d1[u]：u出发的最长链长度
• d2[u]：u出发的次长链长度

状态转移：

int ans = 0;

void dfs(int u, int parent) {
    d1[u] = d2[u] = 0;
    
    for (int v : tree[u]) {
        if (v == parent) continue;
        
        dfs(v, u);
        
        int dis = d1[v] + 1;
        if (dis > d1[u]) {
            d2[u] = d1[u];
            d1[u] = dis;
        } else if (dis > d2[u]) {
            d2[u] = dis;
        }
    }
    
    ans = max(ans, d1[u] + d2[u]); // 更新全局答案
}

4.3 树的重心

问题：删除某点后，最大连通块最小

状态设计：

• size[u]：子树大小
• balance[u]：删除u后的最大连通块大小

状态转移：

int n; // 总节点数
int min_balance = INT_MAX;
int centroid = -1;

void dfs(int u, int parent) {
    size[u] = 1;
    int max_part = 0; // 记录最大连通块大小
    
    for (int v : tree[u]) {
        if (v == parent) continue;
        
        dfs(v, u);
        size[u] += size[v];
        max_part = max(max_part, size[v]); // 子树的连通块
    }
    
    max_part = max(max_part, n - size[u]); // 父节点方向的连通块
    if (max_part < min_balance) {
        min_balance = max_part;
        centroid = u;
    }
}

五、高级技巧与应用

5.1 换根DP（二次扫描）

问题：对每个节点求到其他所有节点的距离和

步骤：

1. 第一次DFS：计算子树信息
2. 第二次DFS：用父节点信息更新子节点

状态转移：

ll down[N]; // 子树距离和
ll up[N];   // 父节点方向距离和
ll size[N]; // 子树大小

// 第一次DFS：计算down和size
void dfs1(int u, int parent) {
    size[u] = 1;
    down[u] = 0;
    
    for (int v : tree[u]) {
        if (v == parent) continue;
        
        dfs1(v, u);
        
        size[u] += size[v];
        down[u] += down[v] + size[v];
    }
}

// 第二次DFS：计算up
void dfs2(int u, int parent) {
    for (int v : tree[u]) {
        if (v == parent) continue;
        
        // 核心换根公式
        up[v] = (up[u] + down[u] - down[v] - size[v]) 
               + (n - size[v]);
        
        dfs2(v, u);
    }
}

5.2 基环树DP

问题：处理带环的树结构

解法：

1. 找环（拓扑排序/DFS）
2. 断环成链
3. 树形DP处理每棵树
4. 合并环上结果

关键代码：

// 1. 找环
vector<int> cycle;
int in_degree[N] = {0};
queue<int> q;

for (int i = 1; i <= n; i++) 
    for (int v : tree[i]) 
        in_degree[v]++;

for (int i = 1; i <= n; i++)
    if (in_degree[i] == 1) q.push(i);

while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : tree[u]) {
        if (--in_degree[v] == 1)
            q.push(v);
    }
}

// 2. 环上节点（in_degree > 1）
for (int i = 1; i <= n; i++)
    if (in_degree[i] > 1) 
        cycle.push_back(i);

// 3. 树形DP（略）
// 4. 环上DP（略）

5.3 长链剖分优化

适用问题：深度相关树形DP

优化效果：O(n)时间复杂度处理子树深度信息

核心思想：直接继承重儿子（最长链）信息，暴力合并轻儿子

代码框架：

int len[N];    // u为起点的最长链长度
int son[N];    // 重儿子（最长链方向）
int *dp[N];    // 指针数组
int buf[N];    // 内存池
int *cur = buf;

void dfs1(int u, int parent) {
    for (int v : tree[u]) {
        if (v == parent) continue;
        dfs1(v, u);
        if (len[v] > len[son[u]]) 
            son[u] = v;
    }
    len[u] = len[son[u]] + 1;
}

void dfs2(int u, int parent) {
    dp[u][0] = 1;
    if (son[u]) {
        dp[son[u]] = dp[u] + 1; // 直接继承重儿子
        dfs2(son[u], u);
    }
    
    for (int v : tree[u]) {
        if (v == parent || v == son[u]) continue;
        dp[v] = cur; cur += len[v]; // 分配内存
        dfs2(v, u);
        for (int j = 0; j < len[v]; j++) {
            dp[u][j+1] += dp[v][j]; // 暴力合并
        }
    }
}

六、树形DP经典问题实战

6.1 二叉搜索子树最大键值和（LeetCode 1373）

问题：在二叉树中找到最大的BST子树

状态设计：

struct Node {
    int min_val, max_val, sum;
    bool isBST;
    Node() : min_val(INT_MAX), max_val(INT_MIN), sum(0), isBST(true) {}
};

Node dfs(TreeNode* u) {
    Node res;
    if (!u) return res;
    
    Node left = dfs(u->left);
    Node right = dfs(u->right);
    
    // 检查BST
    if (left.isBST && right.isBST && 
        (!u->left || left.max_val < u->val) && 
        (!u->right || u->val < right.min_val)) {
        res.isBST = true;
        res.min_val = u->left ? left.min_val : u->val;
        res.max_val = u->right ? right.max_val : u->val;
        res.sum = u->val + left.sum + right.sum;
        ans = max(ans, res.sum); // 更新全局答案
    } else {
        res.isBST = false;
    }
    
    return res;
}

6.2 监控二叉树（LeetCode 968）

问题：用最少的摄像头覆盖所有节点

状态设计：

• 0：未被覆盖
• 1：被覆盖但无摄像头
• 2：有摄像头

状态转移：

int minCameraCover(TreeNode* root) {
    int ans = 0;
    function<int(TreeNode*)> dfs = [&](TreeNode* u) {
        if (!u) return 1; // 空节点视为已覆盖
        
        int left = dfs(u->left);
        int right = dfs(u->right);
        
        // 子节点有未被覆盖的
        if (left == 0 || right == 0) {
            ans++;
            return 2; // 当前节点安装摄像头
        }
        
        // 子节点有摄像头
        if (left == 2 || right == 2) 
            return 1; // 当前节点被覆盖
        
        return 0; // 当前节点未被覆盖
    };
    
    if (dfs(root) == 0) ans++; // 根节点特殊处理
    return ans;
}

七、树形DP优化技巧总结

优化技巧	适用场景	时间复杂度优化	空间复杂度优化
DFS序转线性	树上背包问题	O(n²)→O(n log n)	O(n)
长链剖分	深度相关DP	O(n²)→O(n)	O(n)
虚树	多组关键点查询	O(Σk_i)	O(Σk_i)
重链剖分	路径问题	O(n log n)	O(n)
树上差分	路径更新/子树更新	O(1)更新	O(n)

八、树形DP扩展应用

8.1 树上路径计数

问题：统计满足特定条件的路径数量

解法：点分治 + 树形DP

// 1. 找重心
// 2. 计算子树内路径
// 3. 减去同一子树内的路径

8.2 树上期望问题

问题：随机游走期望步数

解法：列方程 + 树形DP

// 定义状态：dp[u]表示从u到目标的期望步数
// 状态转移：dp[u] = 1 + Σ(dp[v] / deg[u])

8.3 树形数据结构结合

结合树剖：快速处理路径问题

// 树剖预处理
// 树形DP计算子树信息
// 树剖查询路径信息

九、树形DP实战训练

9.1 树的同构判断

解法：树哈希 + 树形DP

const ull P = 131;
ull hash_val[N];

void dfs(int u, int parent) {
    vector<ull> child_hashes;
    for (int v : tree[u]) {
        if (v == parent) continue;
        dfs(v, u);
        child_hashes.push_back(hash_val[v]);
    }
    
    sort(child_hashes.begin(), child_hashes.end());
    hash_val[u] = 0;
    for (ull h : child_hashes) {
        hash_val[u] = hash_val[u] * P + h;
    }
    hash_val[u] = hash_val[u] * P + 1; // 添加当前节点标记
}

9.2 树上最大匹配

问题：选择不相邻边使边权和最大

状态设计：

• dp[u][0]：u不与子节点匹配
• dp[u][1]：u与某个子节点匹配

状态转移：

void dfs(int u, int parent) {
    dp[u][0] = 0;
    dp[u][1] = -INF;
    ll best_gain = -INF;
    
    for (int v : tree[u]) {
        if (v == parent) continue;
        dfs(v, u);
        dp[u][0] += max(dp[v][0], dp[v][1]);
        best_gain = max(best_gain, w[u][v] + dp[v][0] - max(dp[v][0], dp[v][1]));
    }
    
    dp[u][1] = dp[u][0] + best_gain;
}

十、树形DP总结与学习建议

10.1 核心思维导图

10.2 学习路线建议

1. 基础阶段：掌握最大独立集、最小点覆盖
2. 进阶阶段：学习树上背包、树的直径
3. 高级阶段：攻克换根DP、基环树DP
4. 优化阶段：掌握长链剖分、虚树等优化

关键提示：树形DP的核心在于将树的结构与动态规划相结合，通过递归遍历实现自底向上的状态转移。多练习经典问题，培养对状态设计的直觉！

附录：树形DP通用模板（C++11）

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

const int N = 1e5 + 5;
vector<int> tree[N];
int dp[N]; // 根据问题扩展维度

void dfs(int u, int parent) {
    // 初始化边界条件（叶子节点）
    
    for (int v : tree[u]) {
        if (v == parent) continue;
        
        dfs(v, u); // 递归遍历子树
        
        // 状态转移 - 根据具体问题实现
        // dp[u] = merge(dp[u], dp[v]);
    }
    
    // 后处理 - 根据具体问题实现
}

int main() {
    int n;
    cin >> n;
    
    // 建树
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    
    // 初始化DP数组
    memset(dp, 0, sizeof(dp));
    
    // 从根节点开始DFS
    dfs(1, 0);
    
    // 输出结果（通常为dp[1]或全局答案）
    cout << dp[1] << endl;
    
    return 0;
}

通过掌握树形DP的核心思想和经典模型，能够解决各种树形结构上的最优化问题。