树形动态规划：在树上做决策

? 树形动态规划：在树上做最优决策

树形动态规划（树形DP） 是一种针对树状结构（如家族关系、文件目录、组织架构）的优化算法。它的核心思想是：把问题拆解到每个节点，用递归从叶子向根逐步计算出最优解。常见的应用场景包括：“选课方案”（先修课限制）、“最大独立集”（不相邻的节点权重和最大）、“树的直径”等。

对于题目中的“不能同时邀请一对有直接亲子关系的人”这类问题，我们只需要为每个节点定义两种状态（选或不选），然后根据孩子的情况做决策。下面我们就通过多个小例子来拆解它。

? 什么是树形DP？

简单说，树形DP就是把动态规划的状态定义在树的节点上，并利用树的父子关系进行状态转移。它的基本套路是：

• 状态设计：每个节点可能有两个或更多状态，代表不同的决策结果。
• 转移顺序：必须先处理孩子，再处理父节点（后序遍历）。因为父节点的决策依赖于孩子的情况。
• 递归实现：通常用 DFS 从根节点开始，递归到叶子，然后回溯时更新父节点。

生活中的类比：假设你是一家公司的经理，手下有好几个团队组长。你要决定是否给每个团队发“最佳团队奖”，但规则是如果组长获奖，他手下的组员就不能获奖（避免重复）。那么每个组长需要考虑：自己领奖？还是不领奖，让组员们自己去争？这个决策从最底层的员工开始，一层层上报，最终经理（根节点）拍板。这就是树形DP的运作方式。

?‍?‍?‍? 关键概念：状态定义与转移方程

以经典的“参加聚会”问题为例：

• 每个节点（人）有两种状态：

  • dp[u][1]：选择 u 参加聚会，能获得的最大欢乐值。
  • dp[u][0]：不选择 u 参加聚会，能获得的最大欢乐值。

• 转移方程（后序遍历，先处理孩子 v）：

  • 如果选了 u（dp[u][1]），那么所有孩子都不能选，所以 dp[u][1] = happy[u] + sum( dp[v][0] )。
  • 如果不选 u（dp[u][0]），孩子可以选也可以不选，取较大值，即 dp[u][0] = sum( max( dp[v][0], dp[v][1] ) )。

示例：假设一个简单的家庭：爸爸（欢乐值10），有两个儿子大毛（欢乐值5）、二毛（欢乐值8）。大毛又有一个儿子小明（欢乐值12）。

        爸爸 (10)
        /    \
    大毛(5)  二毛(8)
      |
    小明(12)

计算过程：

• 叶子节点小明：没有孩子，所以 dp[小明][1]=12，dp[小明][0]=0。
• 大毛：孩子小明。
  • dp[大毛][1] = 5 + dp[小明][0] = 5 + 0 = 5。
  • dp[大毛][0] = max(dp[小明][0], dp[小明][1]) = max(0,12) = 12。
• 二毛：叶子， dp[二毛][1]=8，dp[二毛][0]=0。
• 爸爸：孩子大毛、二毛。
  • dp[爸爸][1] = 10 + dp[大毛][0] + dp[二毛][0] = 10 + 12 + 0 = 22。
  • dp[爸爸][0] = max(dp[大毛][0], dp[大毛][1]) + max(dp[二毛][0], dp[二毛][1]) = max(12,5) + max(0,8) = 12 + 8 = 20。

最终最大欢乐值 = max(22, 20) = 22。最优方案是：爸爸不选，大毛不选（让小明去），二毛去。或者也可以爸爸去、大毛不去、二毛不去？计算显示爸爸去只有22，比不去（20）大，所以爸爸去、大毛不去（小明也不去？注意：爸爸去时大毛不能去，但小明可以吗？规则是直接亲子关系，不是隔代。所以爸爸去，大毛不能去，但小明是孙辈，可以参加。但在这个问题中，我们只限制直接亲子，所以小明去没问题。但是我们的转移方程里，如果爸爸去，孩子大毛不能去，但大毛的孩子小明可以由大毛的 dp[大毛][0] 决定，而 dp[大毛][0] 已经考虑了小明去或不去的最优值（12）。所以实际上爸爸去，大毛不去，但小明去了，这样总欢乐 = 10 (爸爸) + 12 (小明) + 8 (二毛) = 30？等一下，我们的计算中 dp[爸爸][1] = 10 + dp[大毛][0] + dp[二毛][0] = 10 + 12 + 0 = 22，这里 dp[大毛][0]=12 代表大毛不去时，他的子树（包括小明）的最大值是12，而小明去了正好是12。所以实际上总欢乐是10+12+8？不对，二毛的状态是 dp[二毛][0]=0，意味着二毛没去？还是二毛去了但是孩子没有，所以dp[二毛][0] = 0？不对，dp[二毛][0]应该是 max(0,8) = 8？我之前算错了：对于叶子节点二毛，dp[二毛][0] = max(没有孩子，就是0)？不，叶子节点没有孩子，所以 dp[二毛][0] = 0 对吧？因为不选二毛，欢乐为0，没有可选的子节点。而 dp[二毛][1] = 8。所以 dp[二毛][0]=0，dp[二毛][1]=8。当爸爸不去时，二毛可以选，所以 dp[爸爸][0] = max(dp[大毛][0], dp[大毛][1]) + max(dp[二毛][0], dp[二毛][1]) = max(12,5) + max(0,8) = 12+8=20。当爸爸去时，二毛不能去（因为直接亲子），所以 dp[爸爸][1] = 10 + dp[大毛][0] + dp[二毛][0] = 10+12+0 = 22。这里注意，二毛的儿子？二毛没有孩子，所以 dp[二毛][0]=0。所以总欢乐是10 (爸爸) + 12 (小明) = 22。二毛没去，因为他和爸爸冲突。所以最优是22，选择爸爸和小明参加，大毛和二毛都不去。这个例子很好说明了状态转移。

再给一个身边例子：学校要选“优秀班干部”，要求不能同时选班长和副班长（直接上下级关系），但可以同时选班长和学习委员（学习委员不是直接下级？假设班长管副班长，副班长管学习委员，则直接亲子关系限制只到一层，隔代可同时选）。像这种层层限制的问题，树形DP能轻松搞定。

? 代码实现与注释详解

下面给出完整代码，每行变量名都加了中文注释，方便理解：

#include <iostream>
#include <vector>
#include <algorithm>   // 用max函数
using namespace std;

const int MAXN = 1005;               // 最大节点数
vector<int> children[MAXN];          // children[u]存储u的所有子节点编号
int happy[MAXN];                     // 每个人的欢乐值
int dp[MAXN][2];                     // dp[u][0]：不选u的最大值, dp[u][1]：选u的最大值

// 深度优先遍历，后序计算dp
void dfs(int u) {
    dp[u][1] = happy[u];            // 选u，先加上自己的欢乐
    dp[u][0] = 0;                   // 不选u，当前为0

    // 遍历所有孩子v
    for (int v : children[u]) {
        dfs(v);                     // 先递归计算孩子
        // 如果选了u，孩子都不能选，所以累加孩子不选的值
        dp[u][1] += dp[v][0];
        // 如果不选u，孩子可以选或不选，取最大值累加
        dp[u][0] += max(dp[v][0], dp[v][1]);
    }
}

int main() {
    int n = 5;                      // 总人数
    // 建立树结构：编号从1开始，根节点是1
    children[1].push_back(2);       // 1号的孩子是2
    children[1].push_back(3);       // 1号的孩子是3
    children[2].push_back(4);       // 2号的孩子是4
    children[2].push_back(5);       // 2号的孩子是5
    // 给每个人设定欢乐值
    happy[1] = 10;
    happy[2] = 5;
    happy[3] = 8;
    happy[4] = 12;
    happy[5] = 3;

    // 从根节点开始递归
    dfs(1);

    // 根节点最终有两种可能状态，取最大
    cout << "最大欢乐值: " << max(dp[1][0], dp[1][1]) << endl;
    return 0;
}

代码运行过程解释：

• 递归从根节点1开始，先进入孩子2，孩子2再进入孩子4和5。4和5是叶子，没有孩子，所以它们的dp[4][1]=12, dp[4][0]=0，dp[5][1]=3, dp[5][0]=0。然后回溯到节点2，计算dp[2][1] = 5 + 0 + 0 = 5（因为选了2，孩子4、5都不能选，只能取它们不选的值0），dp[2][0] = max(12,0) + max(3,0) = 12+3=15。接着处理节点3叶子，dp[3][1]=8, dp[3][0]=0。最后回到根节点1，dp[1][1] = 10 + dp[2][0] + dp[3][0] = 10+15+0=25，dp[1][0] = max(dp[2][0],dp[2][1]) + max(dp[3][0],dp[3][1]) = max(15,5) + max(0,8) = 15+8=23，所以最大值为25。

⚠️ 新手常犯的错误

1. 忘记后序遍历：如果先处理父节点再处理孩子，孩子状态还没计算出来，dp值就是垃圾数据。必须先用递归调用孩子，再更新父节点。

2. 状态定义混淆：比如 dp[u][1] 代表选u，但孩子只能取 dp[v][0]；有些人会错误地认为孩子可以选或者不选，导致重复计算冲突。

3. 没有考虑多叉树：代码中 for (int v : children[u]) 要遍历所有孩子，如果少写一个孩子，结果会错。

4. 递归栈溢出：节点数非常大（例如10^5）且树是一条链时，递归深度可能过大。此时需要手动模拟栈或使用非递归方法，但在竞赛中常用递归，需注意栈空间限制（C++可以设置编译器栈大小或使用迭代法）。

5. 根节点不唯一：题目没有明确指出根节点时，需要自己找根（入度为0的节点）。如果建了双向边，还需标记父节点防止循环。

6. 数组大小不够： const int N = 1005; 如果节点数超过1000会越界。实际做题要根据题目范围定义，通常用 const int MAXN = 2e5+5;。

? 完整可运行示例（带输入功能）

为了让代码更通用，下面给出一个可以从标准输入读取树结构的完整版本：

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

const int MAXN = 10010;               // 最大节点数，可根据需要调整
vector<int> children[MAXN];
int happy[MAXN];
int dp[MAXN][2];

void dfs(int u) {
    dp[u][1] = happy[u];
    dp[u][0] = 0;
    for (int v : children[u]) {
        dfs(v);
        dp[u][1] += dp[v][0];
        dp[u][0] += max(dp[v][0], dp[v][1]);
    }
}

int main() {
    int n, root;
    cout << "请输入节点个数（根节点编号为1）：";
    cin >> n;
    // 假设节点编号从1到n，根为1，输入每个节点的父节点（根节点的父节点为0）
    for (int i = 1; i <= n; ++i) {
        int parent;
        cout << "请输入节点" << i << "的欢乐值与父节点编号（空格隔开，根节点父节点为0）: ";
        cin >> happy[i] >> parent;
        if (parent != 0) {
            children[parent].push_back(i);
        } else {
            root = i;   // 找到根
        }
    }

    dfs(root);
    cout << "最大欢乐值为: " << max(dp[root][0], dp[root][1]) << endl;

    return 0;
}

这个版本让用户可以自己输入树的结构，适合练习。

? 相关进阶指引

树形DP不止有“选与不选”两种情况，它还能处理：

• 背包型树形DP：每个节点可以选多种物品（如选课问题，有学分和先修课限制），需要在树上做“分组背包”。
• 换根DP（二次扫描）：当根不确定时，先一次DFS求以某点为根的答案，再通过换根公式计算其他点为根的结果（常用于求树上所有点的最远距离）。
• 树形DP + 状态压缩：比如“树上的最小支配集”可能需要多个状态（自己被选、被父选、被子选）。
• 树形DP + 概率：在树上随机游走求期望，如“树上随机游走覆盖所有点的期望步数”。

如果你熟悉了基本的树形DP，可以继续学习“树上背包”、“换根DP”和“树形DP与DFS序结合”等技巧，它们都是CSP/NOIP比赛中的常考内容。

掌握树形DP，就像拥有了一把解决树上决策问题的万能钥匙——从家庭聚会到公司管理，从选课方案到网络规划，只要数据呈树状结构，都能用树形DP高效求解。