什么是树形DP？

树形动态规划（Tree DP） 是在树形数据结构上进行动态规划的特殊形式。由于树没有环状结构，天然适合使用 DP 处理。树形 DP 通常采用DFS（深度优先搜索） 的顺序，自底向上地计算状态，是算法竞赛中的重要题型。

树形DP的核心思想

1. 树形结构 + 动态规划：利用树的父子关系定义状态
2. 自底向上计算：先计算子树的最优解，再合并到父节点
3. 无后效性：子树的决策不会影响其他子树

常见的树形DP问题

1. 树的最大独立集：选择若干节点，使得没有边相连
2. 树的重心：删除某节点后，使最大子树最小
3. 树的直径：树中最长路径
4. 树上背包：在树上进行背包DP

C++ 代码实现

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

// 树形DP - 树的最大独立集
// 最大独立集：选中的节点之间没有边相连

struct TreeNode {
    int val;
    vector<TreeNode*> children;
    TreeNode(int x) : val(x) {}
};

struct State {
    int select;   // 选择该节点时的最大独立集大小
    int not_select;  // 不选择该节点时的最大独立集大小
};

State dfs_max_independent_set(TreeNode* root) {
    if (!root) return {0, 0};
    
    State state;
    state.select = 1;  // 选择该节点，计数+1
    
    for (auto child : root->children) {
        State childState = dfs_max_independent_set(child);
        
        // 如果选择了当前节点，子节点只能不选
        state.select += childState.not_select;
        
        // 如果不选当前节点，子节点可以选也可以不选，取最大值
        state.not_select += max(childState.select, childState.not_select);
    }
    
    return state;
}

// 树的重心：使得所有子树节点数最大值最小的节点
pair<int, int> find_tree_centroid(int n, const vector<vector<int>>& adj) {
    // 返回 {重心节点, 最大子树大小}
    vector<int> subtree_size(n + 1);
    vector<bool> visited(n + 1, false);
    
    function<int(int)> dfs = [&](int u) -> int {
        visited[u] = true;
        int size = 1;
        int max_subtree = 0;
        
        for (int v : adj[u]) {
            if (!visited[v]) {
                int child_size = dfs(v);
                size += child_size;
                max_subtree = max(max_subtree, child_size);
            }
        }
        
        max_subtree = max(max_subtree, n - size);  // 父方向子树
        subtree_size[u] = size;
        
        return subtree_size[u];
    };
    
    dfs(1);  // 从任意节点开始
    
    // 找重心
    int centroid = 1;
    int min_max_subtree = n;
    
    for (int i = 1; i <= n; i++) {
        int max_sub = max(subtree_size[i], n - subtree_size[i]);
        if (max_sub < min_max_subtree) {
            min_max_subtree = max_sub;
            centroid = i;
        }
    }
    
    return {centroid, min_max_subtree};
}

// 树的直径（最长路径）
pair<int, pair<int, int>> tree_diameter(const vector<vector<int>>& adj) {
    // 返回 {直径长度, {起点, 终点}}
    int n = adj.size() - 1;
    vector<int> dist(n + 1, -1);
    vector<bool> visited(n + 1, false);
    
    function<void(int)> bfs = [&](int start) {
        queue<int> q;
        q.push(start);
        dist[start] = 0;
        visited[start] = true;
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            
            for (int v : adj[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
            }
        }
    };
    
    // 第一次BFS找最远点
    bfs(1);
    int farthest = 1;
    for (int i = 1; i <= n; i++) {
        if (dist[i] > dist[farthest]) farthest = i;
    }
    
    // 第二次BFS从最远点出发
    fill(visited.begin(), visited.end(), false);
    bfs(farthest);
    int other_end = 1;
    for (int i = 1; i <= n; i++) {
        if (dist[i] > dist[other_end]) other_end = i;
    }
    
    return {dist[other_end], {farthest, other_end}};
}

树上背包

在树形结构上进行背包DP，是树形DP的经典应用：

// 树上背包：选择若干节点，总价值最大，受容量限制
void tree_knapsack(int u, int parent, const vector<vector<int>>& adj,
                   const vector<int>& weight, const vector<int>& value,
                   vector<vector<int>>& dp, int W) {
    // dp[v][w] 表示以 v 为根的子树中，容量为 w 时的最大价值
    
    // 初始化：选择当前节点
    dp[u][weight[u]] = value[u];
    
    for (int v : adj[u]) {
        if (v == parent) continue;
        
        tree_knapsack(v, u, adj, weight, value, dp, W);
        
        // 背包合并：将子树的DP结果合并到当前节点
        for (int w = W; w >= 0; w--) {
            for (int k = 0; k + w <= W; k++) {
                if (dp[v][k] > 0) {
                    dp[u][w + k] = max(dp[u][w + k], dp[u][w] + dp[v][k]);
                }
            }
        }
    }
}

完全示例：二叉树的最大独立集

// 构建二叉树
TreeNode* build_tree() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    return root;
}

// 转换为一般树的邻接表表示
void tree_to_adj(TreeNode* root, vector<vector<int>>& adj, int parent = -1) {
    if (!root) return;
    int u = root->val;
    
    for (auto child : root->children) {
        if (child->val != parent) {
            adj[u].push_back(child->val);
            adj[child->val].push_back(u);
            tree_to_adj(child, adj, u);
        }
    }
}

int main() {
    // 示例：树的邻接表表示
    //       1
    //      /|\
    //     2 3 4
    //    /| |\
    //   5 6 7 8
    
    int n = 8;
    vector<vector<int>> adj(n + 1);
    adj[1] = {2, 3, 4};
    adj[2] = {1, 5, 6};
    adj[3] = {1, 7};
    adj[4] = {1, 8};
    adj[5] = {2};
    adj[6] = {2};
    adj[7] = {3};
    adj[8] = {4};
    
    // 1. 树的重心
    auto [centroid, max_sub] = find_tree_centroid(n, adj);
    cout << "树的重心: 节点" << centroid << ", 最大子树大小: " << max_sub << endl;
    
    // 2. 树的直径
    auto [diameter, endpoints] = tree_diameter(adj);
    cout << "树的直径: " << diameter << ", 端点: " 
         << endpoints.first << " - " << endpoints.second << endl;
    
    return 0;
}

复杂度分析

问题	时间复杂度	空间复杂度
最大独立集	O(n)	O(n)
树的重心	O(n)	O(n)
树的直径	O(n)	O(n)
树上背包	O(n × W)	O(n × W)

总结

树形DP是动态规划的重要分支，充分利用了树的结构特性：

• 无环：确保 DP 的无后效性
• 递归结构：自然对应 DP 的递归计算
• 父子关系：清晰的依赖方向

掌握树形DP对于解决复杂的树形问题（如树形区间DP、树形状态压缩DP等）至关重要，也是算法竞赛中不可或缺的技能。