树形DP简介

树形DP是一种特殊的动态规划技术，适用于树形结构的问题。由于树固有的递归性质，树形 DP 一般都是递归进行的。

基本形式

树形DP主要通过dfs遍历树的节点，并在每个节点上计算状态。通常，我们会为每个节点定义一个或多个“状态”，然后通过子节点的状态来计算父节点的状态。

例如：dp[u][0] 和 dp[u][1] 分别表示以节点 u 为根的子树中，当节点 u 不被选中和被选中时的最优解。

选择节点类树形DP

选择节点类树形DP问题通常涉及在树的节点上做出选择，以最大化或最小化某个值，同时满足特定的约束条件。例如：

\begin{cases} dp[u][1] &= \max(dp[v][0], dp[v][1])\\ dp[u][0] &= dp[v][0] \end{cases}

题目描述

某大学有 $n$ 个职员，编号为 $1$ 到 $n$ 。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 $r_i$ ，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

输入格式输入的第一行是一个整数 $n$ 。

第 $2$ 到第 $(n+1)$ 行，每行一个整数，第 $(i+1)$ 行的整数表示 $i$ 号职员的快乐指数 $r_i$ 。

第 $(n+2)$ 到第 $2n$ 行，每行输入一对整数 $l,k$ ，代表 $k$ 是 $l$ 的直接上司。

输出格式输出一行一个整数代表最大的快乐指数。

思路分析

定义状态

对于本题，我们会定义两个状态：

dp[u][0]：表示以节点 u 为根的子树中，当节点 u 不被选中时的最大快乐指数。
dp[u][1]：表示以节点 u 为根的子树中，当节点 u 被选中时的最大快乐指数。

状态转移方程

当节点 u 被选中时，其子节点不能被选中，因此： $dp[u][1] = r_u + \sum_{v \in children(u)} dp[v][0]$
当节点 u 不被选中时，其子节点可以选择被选中或不被选中，因此： $dp[u][0] = \sum_{v \in children(u)} \max(dp[v][0], dp[v][1])$

边界条件

对于叶子节点 u：

如果 u 被选中： $dp[u][1] = r_u$
如果 u 不被选中： $dp[u][0] = 0$

最终结果

最终，我们需要计算根节点的最大快乐指数，即： $\max(dp[root][0], dp[root][1])$

代码实现

#include <bits/stdc++.h>

using namespace std;
#define MAXN (6005)

int n;
int happy[MAXN];
vector<int> child[MAXN];
bool root[MAXN];
int f[MAXN][2];

int dp(int r, int x)
{
    if (f[r][x] != INT_MAX)
    {
        return f[r][x];
    }
    if (child[r].size() == 0)
    {
        f[r][x] = x == 0 ? 0 : happy[r];
        return f[r][x];
    }
    int ans;
    if (x == 0)
    {
        ans = 0;
        for (int c : child[r])
        {
            ans += max(dp(c, 0), dp(c, 1));
        }
    }
    else
    {
        ans = happy[r];
        for (int c : child[r])
        {
            ans += dp(c, 0);
        }
    }
    f[r][x] = ans;
    return ans;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> happy[i];
    }
    for (int i = 0; i < n - 1; i++)
    {
        int l, k;
        cin >> l >> k;
        child[k].push_back(l);
        root[l] = 1;
    }

    int r = 1;
    for (int i = 1; i <= n; i++)
    {
        if (!root[i])
        {
            r = i;
            break;
        }
    }

    // dp[i,0/1]->i为根的树的最优解
    // dp[i,0]=for child: sum(max (dp(child, 0), dp(child,1)))
    // dp[i,1]=sum(dp(child,0))+happy(i)
    fill(&f[1][0], &f[1][0] + n * 2, INT_MAX);
    cout << max(dp(r, 0), dp(r, 1));
    return 0;
}

树上背包

树上背包是背包问题与树形DP的结合。其状态转移方程通常涉及在树的节点上进行选择，同时考虑背包容量的限制。例如：

dp[u][j] = \max(dp[u][j], dp[u][j - w] + val)

题目描述

在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 $N$ 门功课，每门课有若干学分，分别记作 $s_1, s_2, \ldots, s_N$ ，每门课有一门或没有直接先修课（若课程 $a$ 是课程 $b$ 的先修课即只有学完了课程 $a$ ，才能学习课程 $b$ ）。一个学生要从这些课程里选择 $M$ 门课程学习，问他能获得的最大学分是多少？

输入格式第一行包含两个用空格分隔的整数 $N$ 和 $M$ ， $1 \le N \le 300,\qquad 1 \le M \le 300$ 。

接下来的 $N$ 行，第 $i+1$ 行包含两个整数 $k_i$ 和 $s_i$ ：

$k_i$ 表示第 $i$ 门课的直接先修课编号；
$s_i$ 表示第 $i$ 门课的学分。

若 $k_i=0$ 则表示第 $i$ 门课没有直接先修课。变量的取值范围为

0 \le k_i \le N,\qquad 1 \le s_i \le 20,\qquad i=1,2,\dots,N.

输出格式输出一个整数，表示学生能获得的最大学分。

思路分析

由于课程之间存在先修关系，我们可以将这些课程表示为一棵树，其中每个节点代表一门课程，边表示先修关系。假设一个0号节点为没有先修课的课程的虚拟根节点，可以以此节点为根进行dfs。

定义状态

定义 dp[u][j] 表示以节点 u 为根的子树中，最多选择 j 门课程所能获得的最大学分（必须选u自己）。

状态转移方程

对于每个节点 u，我们可以选择不选或选它的子节点。状态转移方程如下：

\text{for each child v of u}:\, dp[u][j] = \max(dp[u][j], dp[v][k] + dp[u][j - k])

其中 v 是 u 的子节点，k 是选择的子节点数量。且：

j \in [1, M + 1]

k \in [0, \min(j - 1, \text{size}(v))]

边界条件

对于某个节点 u：

dp[u][0] = 0，表示不选课程 u
dp[u][1] = s_u，表示选课程 u，但是只能选自己而不选任何子结点

答案的表示

最终答案为 dp[0][M + 1]，即以虚拟根节点为根的子树中，最多选择 M + 1 门课程所能获得的最大学分。因为虚拟节点是必选的，所以需要M + 1。

代码实现

#include <bits/stdc++.h>
using namespace std;

int N, M;
int s[305];
vector<int> f[305];
int dp[305][305];
int sz[305];

void dfs(int u)
{
    sz[u] = 1;
    for (int j = 0; j <= M; j++)
        dp[u][j] = INT_MIN;
    dp[u][0] = 0;
    dp[u][1] = s[u];
    for (int ch : f[u])
    {
        dfs(ch); // 遍历子树，填充dp数组（此时递归填充的是dp[i][*]， i为ch的子孙）
        sz[u] += sz[ch];
        for (int j = M + 1; j >= 1; j--)
        {
            for (int k = 0; k <= min(j - 1, sz[ch]); k++)
            {
                dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[ch][k]);
            }
        }
    }
}
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        int k;
        cin >> k;
        f[k].push_back(i);
        cin >> s[i];
    }

    // 定义dp[u, i, j]表示以u为根的前i棵子树中选了j门课的最优解
    // 则：dp[u,i,j]=max(dp[u,i-1,j-k]+dp[v,num_of_children(v),k])
    // 优化：定义dp[u, j]表示以u为根的中最多选j门课的最优解
    // dp[u,j]=max(dp[u,j], dp[u,j-k]+dp[v,k]) foreach child v, for j = M downto 1, for k = 0 to size(v)
    dfs(0);
    cout << dp[0][M + 1] << endl;
    return 0;
}

关键问题：

为什么要从后往前枚举 j？因为每次更新 dp[u][j] 都累加了之前的状态 dp[u][j - k]，如果从前往后枚举，会导致使用到已经更新过的状态，影响结果的正确性。

可以这样考虑：假设我们能选择任意多的课程，那么最好能把所有的课程都选上，但是由于背包容量的限制，我们只能选择有限的课程。因此，我们考虑先选M门课程，再考虑少选课程的情况。假如无法选择这么多课程，dp 数组中的值不会累加当前结果，从而保持正确性。

但如果从前往后枚举 j，在计算 dp[u][j] 时，就会重复加上之前已经更新过的状态，导致结果错误。例如：如果u->v，并且我们从前往后枚举j：
- 计算 dp[u][2]，dp[u][2] = max(dp[u][2], dp[u][1] + dp[v][1])
- 计算 dp[u][3]，dp[u][3] = max(dp[u][3], dp[u][2] + dp[v][1])，此时dp[u][2]已经被更新过，包含了dp[v][1]，导致重复累计了dp[v][1]的值。
为什么 k 的范围是 0 到 min(j - 1, size(v))？因为在选择子节点 v 的课程时，最多只能选择 j - 1 门课程（因为还要留一门给当前节点 u），同时也不能超过子节点 v 本身的课程数量 size(v)。
怎么计算 size(v)？在 dfs 函数中，我们通过递归计算每个节点的子树大小，并存储在 sz 数组中。每次遍历子节点时，累加子节点的大小即可得到当前节点的大小。

Tree DP 树形DP

树形DP简介

基本形式

选择节点类树形DP

题目描述

思路分析

定义状态

状态转移方程

边界条件

最终结果

代码实现

树上背包

题目描述

思路分析

定义状态

状态转移方程

边界条件

答案的表示

代码实现

关键问题：