介绍

树形dp就是在树上进行dp，常用于 “树上选一组点/边，满足某些条件，且使得某些权值和最大” 的问题。

一般来说，DP的形式为：

设 $dp[i][j]$ 为: 以 $i$ 为根的子树当中，选了 $j$ 个元素得到的最大值。

这样，状态转移就有：

$$dp[u][j] = \max\limits_{to} \{ dp[u][j-k] + dp[to][k]\}$$

代码如下：

for (int j = m; j >= 1; j--) {
    for (int k = 1; k <= j-1; k++) {
        dp[cur][j] = max(dp[cur][j], dp[cur][j-k] + dp[nei][k]);
    }
}

需要注意的点：

  1. 类似于 $01$ 背包，在枚举 j 的值时，要从大到小，防止一个child被重复选择。
  2. 对于依赖关系（例如，child需要依赖parent），可以利用DP过程中，调整状态转移的 上下限 来达到！

时间复杂度：$O(nm^2)$，其中 $n$ 为节点数，$m$ 为第二维的大小。

优化

子树 size 优化

对于一个子树，可能它第二维的上限并没有这么高，我们需要尽量避免枚举一些无用的范围。

我们可以优化一下：

对于每一个root节点 cur，我们记录一下 int sz[cur]，代表 以cur为根的子树的节点数量， 这样枚举的时候我们就可以优化成这样：

for (int j = min(m, sz[cur]); j >= 1; j--) {  //优化
    for (int k = 1; k <= min(j-1, sz[nei]); k++) {  //优化
        dp[cur][j] = max(dp[cur][j], dp[cur][j-k] + dp[nei][k]);
    }
}

例题可见 例1

复杂度：$O(nm)$

DFS序 + 背包 优化

有的时候，第二维表示的不一定是 选择 $j$ 个元素，而可能是背包的一个容量，此时上面的优化的效果就不显著了。

我们可以利用 DFS序 进行优化。

令 $i$ 为 $u$ 的DFS序编号，则对于当前节点 $u$，我们有两种选择：

  1. 选择当前节点：$dp[i+1][j+w_u] = \max \{dp[i][j] + v_u \}$

  2. 不选当前节点：$dp[i + sz_i][j] = \max \{ dp[i][j]\}$

• 第一维度是选到了dfs序中的前 $i$ 项，第二维度就是背包的容量。

解释：

如果选择当前节点，说明可以继续往子树里传递，所以传递到 $dp[i+1][j+w_u]$。

如果不选择当前节点，由于依赖关系，就必须跳过子树，所以传递到 $dp[i + sz_i][j]$。

最终的答案就是 $ans = \max\limits_{j=0}^m \{dp[n+1][j] \}$。

复杂度：$O(nm)$

例题可见 例2

例题

例1 洛谷P2014

题意

有 $N$ 门课程，每门课程有 $1$ 或 $0$ 门前置课程，需要上了前置课程才能上这门课。每门课 $i$ 有 $s_i$ 学分。

现要选 $M$ 门课，使得学分总和最大。

题解

设 $dp[i][j]$ 为: 以 $i$ 为根的子树当中，选了 $j$ 个课程得到的最大值

根据前置课程的关系建图(会发现这是一棵树)，因为有前置课程，所以必须选了root才能选别的，故:

$$dp[i][1] = s_i$$

在处理某一个节点i的时候，$dp[i][j]$ 代表的是： 以它为root的 “已探索” 子树中的最大值，所以在探索各个子树过程中有：

$dp\left[cur\right]\left[j\right]=\max\left(dp\left[cur\right]\left[j\right],dp\left[cur\right]\left[k\right]+dp\left[nei\right]\left[j-k\right]\right),\ k=\left[1,j-1\right]$

实现细节

  1. 我们利用 $dp[i][1] = s_i$ 来处理前置课程，是非常高效的做法！
  2. 状态转移的时候，要 倒序枚举 $j$， 也就是 $j = m … 1$， 因为此时 $dp[cur][k]$ 代表的是已探索的部分，不能包括 $nei$ (因为 $nei$ 正在被探索)。为了防止同一个 $nei$ 被考虑多次，要倒序枚举！
  3. 给定的图可能是一个森林，所以创建一个超级root $0$，并且将 $M$++ (因为 $0$ 肯定要包含进去)，最终答案就是 $dp[0][M+1]$

算法优化

注意，在dp状态转移的时候，我们可能用的是如下loop:

for (int j = m; j >= 1; j--) {
    for (int k = 1; k <= j-1; k++) {
        dp[cur][j] = max(dp[cur][j], dp[cur][j-k] + dp[nei][k]);
    }
}

每个节点 cur 都这样loop一次，总复杂度是 $O(nm^2)$，看起来不可接受。

我们可以优化一下：

对于每一个root节点 cur，我们记录一下 int sz[cur]，代表 以cur为根的子树的节点数量， 这样枚举的时候我们就可以优化成这样：

for (int j = min(m, sz[cur]); j >= 1; j--) {  //优化
    for (int k = 1; k <= min(j-1, sz[nei]); k++) {  //优化
        dp[cur][j] = max(dp[cur][j], dp[cur][j-k] + dp[nei][k]);
    }
}

时间复杂度：$O(n^2)$

证明：我们考虑每一个 nei 被用来转移 的次数，会发现它只会在计算它的 parent 的dp值时才会被拿来统计，又因为每一个节点只有1个parent，所以每个节点对应的子树都只会被统计一次。

所以时间复杂度就是 $T(\sum\limits_{i=1}^n i * sz[i]) = O(n^2)$

更严谨的数学证明可以参见 https://www.luogu.com.cn/blog/Chenxiao-Yan/solution-p4322

luogu-P2014-AC代码 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 305;
const int maxm = 305;

int n,m;
int s[maxn];
int dp[maxn][maxn];
int sz[maxn];  //记录i的子树大小

struct Edge {
    int to, nxt;
} edges[maxm];
int head[maxn], ecnt = 1;

void add(int u, int v) {
    Edge e = {v, head[u]};
    edges[ecnt] = e;
    head[u] = ecnt++;
}

void init() {
    scanf("%d%d",&n,&m);
    fill(head, head+n+2, -1);  //因为存在编号为0的节点，所以初始化为-1
    for (int i = 1; i <= n; i++) {
        int sc,k;
        scanf("%d%d",&k,&sc);
        s[i] = sc;
        add(k, i);
    }
}

void dfs(int cur, int par) {
    if (sz[cur]) return;  // visited
    dp[cur][1] = s[cur];
    sz[cur] = 1;

    for (int e = head[cur]; ~e; e = edges[e].nxt) {
        int nei = edges[e].to;
        if (par == nei) continue;

        dfs(nei, cur);
        sz[cur] += sz[nei];

        for (int j = min(m, sz[cur]); j >= 1; j--) {  //优化
            for (int k = 1; k <= min(j-1, sz[nei]); k++) {  //优化
                dp[cur][j] = max(dp[cur][j], dp[cur][j-k] + dp[nei][k]);
            }
        }
    }
}

int main() {
    init();
    m++;
    dfs(0, -1);
    printf("%d\n", dp[0][m]);
}

如果每门课的前置课程不止1门，就不再是一棵树了，这样的话似乎可以用状压dp来解，leetcode某次比赛中出现过。

例2 洛谷P2515 [HAOI2010]软件安装

题意

给定 $N$ 个软件，每个软件 $i$ 要占用 $W_i$ 的空间，价值为 $V_i$，并且每个软件 $i$ 会依赖最多一个软件 $D_i$。

如果要安装软件 $i$，必须要安装所有的直接/间接依赖软件。

电脑的空间为 $M$，求最大价值。

其中，$1 \leq N \leq 100, 0 \leq M \leq 500, 0 \leq W_i \leq M, 0 \leq V_i \leq 1000, D_i \in [0,N], D_i \neq i$

题解

注意到，本题可能有 循环依赖。

对于循环依赖，直接用 SCC 缩点，剩下的就是一个标准的有依赖背包（本质上，树形DP）问题了：

如果 $i$ 依赖 $D_i$，那么将 $D_i$ 所在的 SCC 连一条有向边，指向 $i$ 所在的 SCC 即可。

另外需要注意，本题可能是一个森林。所以缩点后，对于所有入度为 $0$ 的点 $u$，需要用 $0$ 连一条有向边指向 $u$。

最后，从 $0$ 开始 DP 即可。

DP 的核心代码：

void dfs(int u) {
    if (wei[u] <= m) dp[u][wei[u]] = val[u];
    for (int to : adj2[u]) {
        dfs(to);
        for (int i = m; i >= wei[u]; i--) {
            for (int j = wei[to]; j <= i - wei[u]; j++) {
                dp[u][i] = max(dp[u][i], dp[u][i-j] + dp[to][j]);
            }
        }
    }
}

注意几点：

  1. dp[u][wei[u]] = val[u]; 放在最前面。
  2. DP的过程中，类似于 $01$ 背包，$i$ 是从大到小的，并且下限是 wei[u]。
  3. DP的过程中，$j$ 的下限是 wei[to]，上限是 i - wei[u]（因为 i-j 的有效值必须 $\geq$ wei[u]）。

• 另外，别忘记 tarjan 过程中，更新 low[] 要判断是否在栈内。

树形DP（无优化版本）代码 
#include <bits/stdc++.h>
using namespace std;

int n, m, w[105], v[105], d[105];
int dp[103][503];

vector<int> adj1[103];
set<int> adj2[103];

int dfn[103], low[103], id = 0, st[103], tail = -1;
bool in[103];
int from[103], scc = 0;
void tarjan(int u) {
    in[u] = 1;
    st[++tail] = u;
    dfn[u] = low[u] = ++id;
    for (int to : adj1[u]) {
        if (!dfn[to]) {
            tarjan(to);
            low[u] = min(low[u], low[to]);
        } else if (in[to]) {  // 注意这里有 in[to]
            low[u] = min(low[u], dfn[to]);
        }
    }
    if (low[u] == dfn[u]) {
        from[u] = ++scc;
        while (tail >= 0 && st[tail] != u) {
            int cur = st[tail--];
            in[cur] = 0;
            from[cur] = scc;
        }
        tail--;
        in[u] = 0;
    }
}

void init() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 1; i <= n; i++) cin >> v[i];
    for (int i = 1; i <= n; i++) {
        cin >> d[i];
        if (d[i] == 0) continue;
        adj1[d[i]].push_back(i);
    }

    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }
}

int wei[103], val[103], ind[103];
void rebuild() {
    for (int i = 1; i <= n; i++) {
        int fu = from[i];
        wei[fu] += w[i];
        val[fu] += v[i];
        int fv = from[d[i]];
        if (fu == fv || fv == 0) continue;
        adj2[fv].insert(fu);
        ind[fu]++;
    }
    for (int i = 1; i <= scc; i++) {
        if (!ind[i]) adj2[0].insert(i);
    }
}

void dfs(int u) {
    if (wei[u] <= m) dp[u][wei[u]] = val[u];
    for (int to : adj2[u]) {
        dfs(to);
        for (int i = m; i >= wei[u]; i--) {  // 注意从大到小，注意下限
            for (int j = wei[to]; j <= i - wei[u]; j++) {  // 注意上下限
                dp[u][i] = max(dp[u][i], dp[u][i-j] + dp[to][j]);
            }
        }
    }
}

int main() {
    init();
    rebuild();
    dfs(0);
    int ans = 0;
    for (int i = 0; i <= m; i++) ans = max(ans, dp[0][i]);
    cout << ans << endl;
}
DFS序 优化

我们可以利用 DFS序 进行优化，让时间复杂度从 $O(nm^2)$ 降到 $O(nm)$。

令 $i$ 为 $u$ 的DFS序编号，则对于当前节点 $u$，我们有两种选择：

  1. 选择当前节点：$dp[i+1][j+w_u] = \max \{dp[i][j] + v_u \}$

  2. 不选当前节点：$dp[i + sz_i][j] = \max \{ dp[i][j]\}$

解释：

如果选择当前节点，说明可以继续往子树里传递，所以传递到 $dp[i+1][j+w_u]$。

如果不选择当前节点，由于依赖关系，就必须跳过子树，所以传递到 $dp[i + sz_i][j]$。

最终的答案就是 $ans = \max\limits_{j=0}^m \{dp[n+1][j] \}$。

另外需要注意，由于依赖问题，我们需要 记录每一个节点 $u$ 的所有ancestor的权值和，在枚举的时候，将下限设置为这个权值和。（在代码中，pre[u] 代表 $u$ 所有ancestor的权值和。）

优化代码 
// 注意 idcnt = -1，因为我们是从 0 开始 DFS的！
int mp[103], idcnt = -1, sz[103];  // mp[i]: DFS序为 i 的节点编号 u
int pre[103];  // pre[u] 代表 u 的 ancestor 的 weight的和
void dfs(int u) {
    mp[++idcnt] = u;
    sz[u] = 1;
    for (int to : adj2[u]) {
        pre[to] = pre[u] + wei[u];  // ancestor的权值和
        dfs(to);
        sz[u] += sz[to];
    }
}


void solve() {
    for (int i = 1; i <= scc; i++) {
        int u = mp[i];
        for (int j = pre[u]; j <= m; j++) {  // 注意枚举下限从 pre[u] 开始
            dp[i+sz[u]][j] = max(dp[i+sz[u]][j], dp[i][j]);  // 不选

            if (j + wei[u] <= m)  // 选择（要保证 j+wei[u] <= m）
                dp[i+1][j+wei[u]] = max(dp[i+1][j+wei[u]], dp[i][j] + val[u]);
        }
    }
}

int main() {
    init();
    rebuild();
    dfs(0);
    solve();
    int ans = 0;
    for (int j = 0; j <= m; j++) ans = max(ans, dp[scc+1][j]);  // 注意是 scc+1
    cout << ans << endl;
}

例3 洛谷P4395 [BOI2003]Gem 气垫车

题意

给一棵 $n$ 个节点的树，要求给所有节点标上正整数权值，使得相邻节点不能权值相同，求最小总权值。

其中，$n \leq 10^4$。

题解

第一眼看过去是个树染色问题，要么权值为 $1$，要么为 $2$。

很遗憾这个做法是错的，考虑一下这个数据，两个菊花接在一起：

img

这里很明显应该给 $1,2$ 分别标上 $2,3$ 的权值，其余全部标 $1$。

所以我们暴力枚举一下每个节点上可能标什么权值就好了，直觉上告诉我们这个上限不会太大。

然后利用树形DP来求最小值即可。

代码中取了上限 $M = 55$，所以复杂度就是 $O(55^2 * n)$

代码 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10005;
const int M = 55;

struct Edge {
    int to, nxt;
} edges[maxn<<1];
int head[maxn], ecnt = 1, n, m;
int dp[maxn][M+3];
void addEdge(int u, int v) {
    Edge e = {v, head[u]};
    head[u] = ecnt;
    edges[ecnt++] = e;
}

void dfs(int u, int p) {
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
        dfs(to, u);
        for (int j = 1; j <= M; j++) {
            int r = 1e9;
            for (int k = 1; k <= M; k++) {
                if (j == k) continue;
                r = min(r, dp[to][k]);
            }
            dp[u][j] += r;
        }
    }
    for (int j = 1; j <= M; j++) dp[u][j] += j;
}

int main() {
    fastio;
    cin >> n;
    for (int i = 1; i <= n-1; i++) {
        int u,v; cin >> u >> v;
        addEdge(u,v);
        addEdge(v,u);
    }
    dfs(1, 0);
    int ans = 1e9;
    for (int j = 1; j <= M; j++) ans = min(dp[1][j], ans);
    cout << ans << endl;
}

例4 洛谷P3177 [HAOI2015]树上染色

题意

给定一棵 $n$ 个节点的树，树的边上有权值。

给定一个整数 $k \in [0,n]$，要求从树上选择 $k$ 个点，将其染成黑色，剩余的染成白色。

染色后，获得的价值为 黑点两两之间的距离之和 + 白点两两之间的距离之和。

求最大价值？

其中，$n,k \leq 2000$。

题解

数据范围看起来就非常树形DP。

设 dp[u][i] 为在 $u$ 的子树内，染 $i$ 个黑点的总价值。

现在考虑一下怎么转移？

如果我们直接进行转移，就需要维护节点的深度之和，然而这很明显不现实，所以我们可以 考虑每条边 的贡献。

假设考虑的子树 $v$ 中，染了 $j$ 个黑点，那么一条边 $(u,v,w)$ 的贡献刚好就是：

$$w * (j * (k-j) + (sz[to] - j) * (n - k - sz[to] + j))$$

其中 j * (k-j) 是这条边两端的黑点数量的乘积，而 (sz[to] - j) * (n - k - sz[to] + j) 就是这条边两端的白点数量的乘积。

然后直接转移就可以了（注意第二维度的转移顺序是从 $0$ 开始，否则会导致 $dp[u][i]$ 被更新两次），注意一下使用 sz[] 进行时间复杂度优化到 $O(n^2)$，否则是 $O(n^3)$。

代码 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2003;

ll dp[maxn][maxn];
ll sz[maxn];
int n,k;
struct Edge {
    int to, nxt;
    ll w;
} edges[maxn<<1];
int ecnt = 1, head[maxn];
void addEdge(int u, int v, ll w) {
    Edge e = {v, head[u], w};
    head[u] = ecnt;
    edges[ecnt++] = e;
}

void dfs1(int u, int p) {
    sz[u] = 1;
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
        dfs1(to, u);
        sz[u] += sz[to];
    }
}

void dfs(int u, int p) {
    dp[u][0] = dp[u][1] = 0;
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
        dfs(to, u);
        ll w = edges[e].w;

        for (ll i = (ll)min((ll)k, sz[u]); i >= 0; i--) {   // u 用多少个黑
            for (ll j = 0; j <= min(i,sz[to]); j++) {  // v 用多少个黑
                ll cnt = j * (k - j) + (sz[to] - j) * (n - k - sz[to] + j);
                dp[u][i] = (ll)max(dp[u][i], dp[u][i-j] + dp[to][j] + cnt * w);
                // j = 0 开始: dp[u][i], dp[u][i-1] ... (正确)
                // j = min(i,sz[to]) 开始: dp[u][0], dp[u][1], ..., dp[u][i] -> 这导致 dp[u][i] 被更新了两次
            }
        }
    }
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n-1; i++) {
        int u,v; ll w; cin >> u >> v >> w;
        addEdge(u,v,w); addEdge(v,u,w);
    }
    for (int i = 1; i <= n; i++)
        for (int j = 2; j <= k; j++) dp[i][j] = -1e18;
        
    dfs1(1, 0);
    dfs(1, 0);
    cout << dp[1][k] << endl;
}

注意事项

  1. 本题枚举 $i,j$ 时，注意要加上 $sz[u], sz[to]$ 作为上限来优化。
  2. 注意初始化 $dp[i][j]$ 为负无穷，并且设 $dp[i][0] = dp[i][1] = 0$。
  3. 注意第二维度的转移顺序（第一维倒序这个是必须的）。

例5 [1到n经过特定点的最短路]

题意

给定 $n$ 个节点的一棵树，树上有 $m$ 个点被标记了，求从节点 $1$ 走到节点 $n$，中途需要经过这些标记点的最短路长度，所有边权值为 1。

其中，$n \leq 2 \times 10^5$。

题解

• 这是一道群里传的题目，没有代码。

首先将 $1$ 到 $n$ 的路径拉成一条链，链上所有的点一定会被经过，不用管。

接下来就是挂在链上的若干子树，对于每个子树，思考如下问题：

从一棵树的根出发，经过树内的所有标记点，再回到这棵树的根，需要的最短路长度？

对于这个问题，我们考虑对于每个被标记的点 $u$，从根（假设为 $1$）到 $u$ 的路径一定会被经过，被经过的这些边被打上标记，代表这些边一定会被经过。

打完标记后，我们知道在最优解中，每条边一定会被经过 $2$ 次，所以答案就是标记边 $*2$。

如何打标记？

只要一次dfs即可，每次dfs时判断这个子树里面有没有需要标记的点，如果有，这条边就打上标记。

例6 NAQ2017E. Company Picnic

题意

给定一棵树，每个节点有权值 $w_i$。

定义一组节点为：两个直接相连的节点 $i,j$，这组节点的权值定义为 $\min (w_i,w_j)$。

求选出若干组节点的方法，使得每组节点用到的点各不相同，并且满足选出节点组数最多。

在节点组数量最多的情况下，求出这些节点的权值和最大值。

其中，$2 \leq n \leq 1000, w_i \in [2.2,5.3]$。

题解

这个题需要维护最多节点组数，还要维护权值和最大值。所以 dp 数组维护两个值。

定义 $dp(u,0)$ 为：$u$ 的parent没有选它，$dp(u,1)$ 则是选了它的。

dp 值则是一个pair：<int, double>，代表子树中最大的节点组数，以及对应的最大权值和。

在转移的时候，注意到 $dp(u,1)$ 不能选任何 $dp(v,1)$ 转移。而 $dp(u,0)$ 只能选一个 $dp(v,1)$ 转移（或者也可以不选）。

转移的过程中，优先更新第一个值（节点组数），如果第一个值相等，再更新第二个值（权值和最大值）。

代码 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e3+5;

pair<int,double> dp[maxn][2];
vector<string> adj[maxn];
map<string, int> mp;
double sp[maxn];
struct Edge {
    int to, nxt;
} edges[maxn<<1];
int head[maxn], ecnt = 1;
void addEdge(int u, int v) {
    Edge e = {v, head[u]};
    edges[ecnt] = e;
    head[u] = ecnt++;
}
int rt;

void dfs(int u, int p) {
    int cnt = 0, b = 0;  // b: 最优转移 1 的点v
    double sum = 0;
    // 0 的情况
    for (int e = head[u]; e; e = edges[e].nxt) {
        int v = edges[e].to;
        if (v == p) continue;
        dfs(v, u);
        cnt += dp[v][0].first;
        sum += dp[v][0].second;
        if (b == 0) b = v;
        else if (dp[v][1].first - dp[v][0].first > dp[b][1].first - dp[b][0].first) {
            b = v;
        } else if (dp[v][1].first - dp[v][0].first == dp[b][1].first - dp[b][0].first && 
            min(sp[u], sp[v]) + dp[v][1].second - dp[v][0].second > min(sp[u], sp[b]) + dp[b][1].second - dp[b][0].second) {
            b = v;
        }
        
    }

    if (!b) return;

    cnt -= dp[b][0].first;
    cnt += dp[b][1].first;
    sum -= dp[b][0].second;
    sum += min(sp[u], sp[b]) + dp[b][1].second;

    dp[u][0].first = cnt + 1;
    dp[u][0].second = sum;

    cnt = 0, sum = 0;
    for (int e = head[u]; e; e = edges[e].nxt) {
        int v = edges[e].to;
        if (v == p) continue;
        cnt += dp[v][0].first;
        sum += dp[v][0].second;
    }
    dp[u][1].first = cnt;
    dp[u][1].second = sum;

    if (cnt > dp[u][0].first || (cnt == dp[u][0].first && sum > dp[u][0].second)) {
        dp[u][0].first = cnt;
        dp[u][0].second = sum;
    }
}

int main() {
    fastio;
    int n; cin >> n;
    int id = 0;
    for (int i = 1; i <= n; i++) {
        string s; cin >> s;
        if (!mp.count(s) && s != "CEO") mp[s] = ++id;
        double w; cin >> w;
        string t; cin >> t;
        if (!mp.count(t) && t != "CEO") mp[t] = ++id;

        int u = mp[s], v = mp[t];
        if (t == "CEO") {
            rt = u;
        } else { 
            addEdge(u,v);
            addEdge(v,u);
        }
        sp[u] = w;
    }
    dfs(rt, -1);
    cout << dp[rt][0].first << " " << dp[rt][0].second / dp[rt][0].first << "\n";
}