树形 DP，顾名思义，就是在树上的 DP．

树形 DP 有以下特征：

转移方程一般从当前点的子树转移而来
转换方程的第一维 n 一般表示以 n 为根的子树，怎么怎么样．
一般来说，树的叶子节点是初始状态，根节点是最终状态
一般会综合所有子节点
树形 DP 的实现类似后序遍历．
树形 DP 和线性 DP 有关联，有时候可以相互转化．

树形 DP 一般只有两个顺序：从上往下（不常见）、从下往上，因此，表达式中不能同时存在子节点信息和父节点信息（即无后效性）

典型案例#

树的大小#

给定一棵树，需要统计树中有多少子节点．

这个问题很简单：

状态定义：dp[u] 表示以 u 为根节点的树中有多少子节点．
初始状态：dp[l]=1，其中 l 是叶子节点．
状态转移：dp[u]=sum(dp[v])+1，其中 v 是 u 的子节点．即 dp[u] 为其所有子节点之和再加上本身．
最终状态：dp[r]，r 是根节点．

最大独立集#

题目：P1352 没有上司的舞会

某大学有 $n$ 个职员，编号为 $1\ldots n$ ．

他们之间有从属关系，员工 $k$ 是员工 $l$ 的直接上司，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司．

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

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

对于 $100\%$ 的数据，保证 $1\leq n \leq 6 \times 10^3$ ， $-128 \leq r_i\leq 127$ ， $1 \leq l, k \leq n$ ，且给出的关系一定是一棵树．

在这里，会用到影响参数化的思想．

状态定义：dp[u][s] 表示以 u 为根节点的树中员工（即员工 u 的间接或直接下属）的最大快乐指数，s 表示员工 u 是（1）否（0）会参加舞会
初始状态：dp[l]=r[l]，其中 l 是叶子节点．
状态转移： $dp[u][0] = max(dp[v][0], dp[v][1], 0)$ ， $dp[u][1] += max(dp[v][0], 0)+r[u]$ ，其中 v 是 u 的子节点．即 dp[u][0] 为其所有子节点去或不去所得的最大值，dp[u][1] 为其所有子节点不去所得的最大值．
最终状态：max(dp[r][0],dp[r][1])，r 是根节点．

标程

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

4
const int N = 6e3 + 100;
5

6
int n, r[N], dp[N][2], fa[N];
7
vector<int> e[N];
8

9
void dfs(int u) {
10
    for (int i = 0; i < e[u].size(); i++) {
11
        int v = e[u][i];
12
        dfs(v);
13
        dp[u][0] += max(max(dp[v][0], dp[v][1]), 0);
14
        dp[u][1] += max(dp[v][0], 0);
15
    }
16
    dp[u][1] += r[u];
17
}
18

19
int main() {
20
    cin >> n;
21
    for (int i = 1; i <= n; i++) {
22
        cin >> r[i];
23
    }
24
    for (int i = 1; i <= n - 1; i++)
25
    {
26
        int l, k;
27
        cin >> l >> k;
28
        e[k].push_back(l);
29
        fa[l] = k;
30
    }
31
    int root = 1;
32
    while (1) {
33
        if (fa[root] == 0) break;
34
        root = fa[root];
35
    }
36
    dfs(root);
37
    cout << max(dp[root][0], dp[root][1]);
38
    return 0;
39
}

换根 DP#

题目：P3478 STA-Station

给定一个 $n$ 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大．

一个结点的深度之定义为该节点到根的简单路径上边的数量．

对于全部的测试点，保证 $1 \leq n \leq 10^6$ ， $1 \leq u, v \leq n$ ，给出的是一棵树．

想法一：暴力枚举#

尝试以 $O(n)$ 枚举每一个点，然后再通过 dfs 统计一遍答案，总计 $O(n^2)$

想法二#

考虑将根上移带来的贡献．

定义：

sz[t] 表示在 1 为根节点的树中，以 t 为根节点的子树的节点数量．
low[t] 表示在 1 为根节点的树中，以 t 为根的子树中所有节点到节点 t 的距离之和．
dp[t] 表示在 t 为根节点的树中，书中所有节点到节点 t 的距离．

sz[t] 很好求，参考树的大小一节．

第一个 dfs 求 low 时，从下到上，有：

low[u]=sz[u] - 1 +\sum_{u\rightarrow v} low[v]

在上面的式子中：

$sz[u]-1$ 表示边 $u \rightarrow v$ 这条边所做的贡献．
$\sum low[v]$ 表示其子节点的贡献．

边界条件：无需边界条件，所有节点都是自洽的，即使是根节点．

第二个 dfs 求 dp 时，考虑若将根节点从 u 改成 v，v 是 u 的子节点，则有以下变化：

不位于节点 v 下面的节点（不包括 v，共计 $n-sz[v]$ 个节点）每一个到根节点的距离增大 1
位于节点 v 下面的节点（包括 v，共计 $sz[v]$ 个节点）每一个到根节点的距离减少 1

则从上到下，有：

dp[v] = dp[u]+(n-sz[v])-(sz[v])

化简一下，就是：

dp[v]=dp[u]+n-2*sz[v]

考虑边界条件：当 v 是根节点时， $dp[v] = low[v]$

整个题的最终状态为： $max(dp[t]),t\in \mathbb{Z},1\leq t\leq n$

时间复杂度为 $O(n)$

标程：

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

4
const int N = 1e6 + 100;
5

6
int n, f[N], sz[N], vis[N];
7
long long dp[N];
8
int low[N];
9
vector<int> ee[N], e[N];
10

11
void build(int u, int fa = 0) {
12
    if (vis[u]) return;
13
    vis[u] = true;
14
    if (fa != 0) e[fa].push_back(u);
15
    for (auto it : ee[u]) {
16
        build(it, u);
17
    }
18
}
19

20
void dfs_sz(int u) {
21
    for (auto it : e[u]) {
22
        dfs_sz(it);
23
        sz[u] += sz[it];
24
    }
25
    sz[u]++;
26
}
27

28
void dfs_1(int u) {
29
    low[u] = sz[u] - 1;
30
    for (auto v : e[u]) {
31
        dfs_1(v);
32
        low[u] += low[v];
33
    }
34
}
35

36
void dfs_2(int u) {
37
    for (auto v : e[u]) {
38
        dp[v] = dp[u] + n - 2 * sz[v];
39
        dfs_2(v);
40
    }
41
}
42

43
int main() {
44
    ios::sync_with_stdio(false);
45
    cin.tie(0);
46
    cout.tie(0);
47
    cin >> n;
48
    for (int i = 1; i < n; i++) {
49
        int u, v;
50
        cin >> u >> v;
51
        ee[u].push_back(v);
52
        ee[v].push_back(u);
53
    }
54
    int root = 1;
55
    build(root);
56
    dfs_sz(root);
57
    dfs_1(root);
58
    dp[root] = low[root];
59
    dfs_2(root);
60
    long long ans = -1, ans_id = -1;
61
    for (int i = 1; i <= n; i++) {
62
        if (ans < dp[i]) {
63
            ans = dp[i];
64
            ans_id = i;
65
        }
66
    }
67
    cout << ans_id;
68
    return 0;
69
}

树形背包#

题目：P2014 选课

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

题目保证课程安排无冲突．（即不会有 $a$ 是 $b$ 的先修课， $b$ 也是 $a$ 的先修课这类情况存在．）

对于 $100\%$ 数据，保证 $1 \leq N \leq 300$ , $1 \leq M \leq 300$ , $1 \leq {s_i} \leq 20$ ．

数据保证至少存在一个 $k_i=0$ ，即至少一门课无先修课．

和 01 背包相类似，定义 dp[t][k] 表示在以 t 为根的子树中，选择 k 门进行学习，所能够获得的最大分数．

由于此图是一个森林，可以将所有没有父节点的节点都归属到节点 0 下，让整个图成为一棵树．相应的，由于必须需要学习课程 0，所以 $m$ 会增加 1．

此时，初始状态为 $dp[t][1]=s[t],t\in \mathbb{Z},1\leq t\leq n$ ，最终状态为 dp[root][m]，root 是根节点．

但状态转移方程是什么呢？

我们要将 k 门学习学科的配额进行有效分配．对于每一门学科，又可以分配 $[0,n]$ 个可学习配额，因此，有：

dp[u][k] = \max(\sum_{u\rightarrow v} dp[v][a_i]) + s[u],0\leq a_i\leq k,\sum_{u\rightarrow v}a_i=k-1

，即：

对于每一种分配方案，为每一个子节点分配一定的可学习科目额度 $a_i$ ，所有可学习科目额度之和恰好等于 $k-1$ （这是由于节点 $u$ 必修，如果不修节点 $u$ ，则无法学习其子节点）．
对于所有分配方案，取其中收益最大的．

那要通过超高的时间复杂度来枚举每一种情况并计算吗？

我们可以引入一个辅助数组 g[m][k]，表示已经考虑 m 个 u 的子节点，且使用了 k 个学习配额，所能够获得的最大收益．

则有初始状态 $g[0][1]=s[u]$ ，即只选择根节点 $u$ 时的情况．

不难发现状态转移方程： $g[m][H] = g[m-1][A]+dp[v_m][H-A],0\leq A\leq H$ ，其实就是在增加一个子节点时，枚举这个子节点所得的配额 $A$ ，用一种类似打擂台的方法统计出结果．使用完 g 数组后一定要清空！！！

利用 g 数组来优化 dp 的状态转移方程：

\forall k,dp[u][k] = g[v_{max}][k]

， $v_{max}$ 为节点 $u$ 的子节点数量．必须选取节点 $u$ ，因为如果不选取节点 $u$ ，节点 $u$ 中的所有子节点都无法被选取．时间复杂度 $O(n^2)$ ．

标程：

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int N = 305;
4
const int INF = 0x3f3f3f3f;
5
int n, m, s[N], root;
6
vector<int> e[N];
7
int dp[N][N], g[N][N], sz[N];
8

9
void dfs_sz(int u) {
10
    sz[u] = 1;
11
    for (int v = 0; v < e[u].size(); v++) {
12
        dfs_sz(e[u][v]);
13
        sz[u] += sz[e[u][v]];
14
    }
15
}
16

17
void dfs(int u) {
18
    for (int v : e[u])
19
        dfs(v);
20

21
    int son_cnt = e[u].size();
22
    // 初始化 g 为 -INF
23
    for (int i = 0; i <= son_cnt; ++i)
24
        for (int j = 0; j <= m; ++j)
25
            g[i][j] = -INF;
26
    g[0][1] = s[u];
27

28
    int tot_sz = 1;
29
    for (int i = 0; i < son_cnt; ++i) {
30
        int v = e[u][i];
31
        for (int j = 1; j <= tot_sz; ++j) {
32
            if (g[i][j] == -INF)
33
                continue;
34
            // 不选 v
35
            g[i + 1][j] = max(g[i + 1][j], g[i][j]);
36
            // 选 v 的 k 门课
37
            for (int k = 1; k <= sz[v]; ++k) {
38
                if (dp[v][k] == -INF)
39
                    continue;
40
                int nj = j + k;
41
                if (nj > m)
42
                    break;
43
                g[i + 1][nj] = max(g[i + 1][nj], g[i][j] + dp[v][k]);
44
            }
45
        }
46
        tot_sz += sz[v];
47
    }
48

49
    for (int j = 1; j <= min(tot_sz, m); ++j)
50
        dp[u][j] = g[son_cnt][j];
51
}
52

53
int main() {
54
    cin >> n >> m;
55
    m++;
56
    for (int i = 1; i <= n; i++) {
57
        int k;
58
        cin >> k >> s[i];
59
        dp[i][1] = s[i];
60
        e[k].push_back(i);
61
    }
62

63
    for (int i = 1; i <= n; i++) {
64
        for (int j = m; j <= m; j++) {
65
            dp[i][j] = -INF;
66
        }
67
    }
68

69
    dfs_sz(0);
70
    dfs(0);
71
    cout << dp[0][m] << endl;
72
}

音乐

音乐

典型案例#

树的大小#

最大独立集#

换根 DP#

想法一：暴力枚举#

想法二#

树形背包#

文章分享

音乐

树形DP

典型案例#

树的大小#

最大独立集#

换根 DP#

想法一：暴力枚举#

想法二#

树形背包#

文章分享