树形 DP | CmsBlog

树形 DP，即在树上进行的 DP。由于树固有的递归性质，树形 DP 一般都是递归进行的。

树形 DP 的架构

首先，我们要把这个树建好，通常我们把读入的边建立双向的，即如果 $u$ 与 $v$ 相连，建立 $u \to v$ 以及 $v \to u$ 。

来看一下树形 DP 伪代码。

void dfs(u,fa,other): // 因为是棵树，所以我们用递归遍历每个节点。fa 是 u 的父节点，other 是其它传参
    if special
        do  sth // 如果这个节点有什么特殊之处特别计算
    for each v (存在 u->v)
        if v=fa continue //我们在建树过程中建的是双向边，会与父亲相连，需要特判
        dfs(v,u) // 一般是先将子树的 dp 值算好
        do dp // 计算 u 的 dp 值（一般是通过子树的值）

模板题

没有上司舞会（简单树形 DP）

思路

本题是树形 $dp$ 模板题，根据树形 $dp$ 的常规方法，不妨令 $dp$ 的第一维表示以i为根节点的子树上，此时定会有两个保留信息——当 $i$ 参加时快乐指数的最大值与i不参加时快乐指数的最大值。
不妨假设 $F[x , 0]$ 表示以 $x$ 为根节点且 $x$ 不参加舞会时快乐指数的最大值， $F[x,1]$ 表示以 $x$ 为根节点且 $x$ 参加舞会时快乐指数的最大值。

首先讨论 $x$ 不参加舞会时，此时还需要分类讨论（ $x$ 的儿子可以邀请或不邀请），分析至此，不难列出第一个状态转移方程：

F[x , 0] = \sum_{s\in Son(x)}\max(F[s,0],F[s,1])

再则讨论 $x$ 参加舞会时，此时 $x$ 的儿子只有一种情况——不参加舞会，分析至此，不难列出第二个状态转移方程：

F[x , 0] = \sum_{s\in Son(x)}F[s,0]

其中 $Son(x)$ 表示 $x$ 的儿子集合
分析至此，不难写出程序。只需枚举出校长（没有上司的节点，即 $root$ ），然后递归求解即可

目标 $max(F[root,0],F[root,1])$

参考程序

#include <bits/stdc++.h>
using namespace std;
inline int read(){
    int f = 1 , ret = 0;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        ret = (ret << 3) + (ret << 1) + c - 48;
        c = getchar();
    }
    return f * ret;
}
int n , root;
vector<int> Son[10010] ;
int h[10010] , v[10010] , f[10010][2];
void dp(int y){
    f[y][0] = 0;
    f[y][1] = h[y];
    for(int i = 0;i < Son[y].size();i++){
        int x = Son[y][i];
        dp(x);
        f[y][0] += max(f[x][1] , f[x][0]);
        f[y][1] += f[x][0];
    }
}
int main(){
    n = read();
    for(int i = 1;i <= n;i++){
        h[i] = read();
    }
    for(int i = 1;i < n;i++){
        int x , y;
        x = read() , y = read();
        v[x] = 1;//x has a father
        Son[y].push_back(x);//x is a son of y
    }
    for(int i = 1;i <= n;i++){
        if(!v[i]){//v[i] == 0
            root = i;//i doesn't has father
            break;
        }
    }
    dp(root);
    cout << max(f[root][0] , f[root][1]) << endl;
    return 0;
}

树形 dp 除了可以递归的从上到下求解，还可利用拓扑排序从下到上dp

先来回顾一下，拓扑排序的时候我们其实是从根到子节点，那么如何实现从子节点返回根节点的求解过程呢？反向连边存入度。没错，反向，就可以轻易实现这样的求解。可以自己手动模拟一下。然后对于这样的求解，我们可以在边求拓扑排序边更新答案。
通常递归已经够用，再次不做赘述 ~~其实就是不会~~

CTSC1997选课

思路

首先要处理森林，题目给的暗示很明显，就是建立0节点为虚拟节点连不同的连通块。

设计状态： $dp[i][j][0/1]$ 表示以i为根的子树选j个，其中i选不选的最大学分。

分析一下性质，对于一棵子树来讲，这个子树根节点必须要选，否则整个子树一个都选不了。于是就可以把最后一维压掉。

变成： $dp[i][j]$ 表示以i为根的子树选j个的最大学分。

然后就相当于一个背包了。转移方程如下：

dp[x][j]=max(dp[x][j],dp[x][j-k]+dp[y][k])(k∈[0,j])

初值是 $dp[i][1]=w[i]$ ，比较好理解。

这里需要注意dp转移的顺序问题，需要知道的是，对于状态 $dp[x][j]$ ，要由 $dp[x][j−k]$ 转移过来，所以需要保证在转移 $dp[x][j]$ 的时候， $dp[x][j-k]$ 还没有被转移，这样才能符合线性 $DP$ 的原则。

参考代码

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

vector<int> G[1010];

int N , M , Dp[1010][1010];

void Dynamic_Programming(int root) {
	for(int i = 0; i < G[root].size(); i++) {
		Dynamic_Programming(G[root][i]);
		for(int j = M + 1; j >= 1; j--) {
			for(int k = 0; k < j; k++) {
				Dp[root][j] = max(Dp[root][j] , Dp[G[root][i]][k] + Dp[root][j - k]);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> N >> M;
	for(int i = 1; i <= N; i++) {
		int Fa;
		cin >> Fa >> Dp[i][1];
		G[Fa].push_back(i);
	}
	Dynamic_Programming(0);
	cout << Dp[0][M + 1] << endl;
	return 0;
}