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

树形 DP 的架构

首先,我们要把这个树建好,通常我们把读入的边建立双向的,即如果 uuvv 相连,建立 uvu \to v 以及 vuv \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)

思路

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

首先讨论 xx 不参加舞会时,此时还需要分类讨论(xx 的儿子可以邀请或不邀请),分析至此,不难列出第一个状态转移方程:

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

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

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

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

目标 max(F[root,0],F[root,1])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]dp[i][j][0/1] 表示以i为根的子树选j个,其中i选不选的最大学分。

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

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

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

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

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

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

参考代码

#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;
}