树形DP详细解析

linbaicheng / 2023-08-27 / 原文

1.基本定义

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

2.模板题

Acwing 285. 没有上司的舞会

思路

我们设 \(f(i,0/1)\) 代表以 i 为根的子树的最优解（第二维的值为 \(0\) 代表 \(i\) 不参加舞会的情况，\(1\) 代表 \(i\) 参加舞会的情况）。

对于每个状态，都存在两种决策（其中下面的 \(x\) 都是 \(i\) 的儿子）：

1.上司不参加舞会时，下属可以参加，也可以不参加，此时有 \(f(i,0) = \sum\max \{f(x,1),f(x,0)\}\)；
2.上司参加舞会时，下属都不会参加，此时有 \(f(i,1) = \sum{f(x,0)} + a_i\)。

于是我们可以通过 \(DFS\)，在返回上一层时更新当前结点的最优解。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
//#define int long long

using namespace std;

#define N 6010
#define For(i,j,k) for(int i=j;i<=k;i++)
#define IOS ios::sync_with_stdio(0),cin.tie(),cout.tie()

int n, m, idx = 0, ok[N], vis[N], dp[N][2];
int h[N], e[N], ne[N];

void add (int a, int b) {
	e[++ idx] = b, ne[idx] = h[a], h[a] = idx;
} //建边

void dfs (int dep) {
	vis[dep] = 1; //将这个点打上标记

	for (int i = h[dep]; i; i = ne[i]) {
		if (vis[e[i]]) continue; //如果用过，跳出
		dfs (e[i]); //递归枚举子树
		dp[dep][1] += dp[e[i]][0]; //使用这个点的价值首先包含不使用这个点的价值
		dp[dep][0] += max (dp[e[i]][0], dp[e[i]][1]); //不取这个点的价值包含选或不选子节点的最大价值
	}
}

int main () {
	IOS;
	cin >> n;
	For (i, 1, n) {
		cin >> dp[i][1];
	} //输入值可视为使用第 i 个点的最大价值

	For (i, 1, n - 1) {
		int x, y;
		cin >> x >> y; //建边，同时标记 x 点有父亲
		ok[x] = 1, add (y, x);
	}

	For (i, 1, n) {
		if (!ok[i]) { 
			dfs (i); //如果发现根节点，就递归查找
			cout << max (dp[i][1], dp[i][0]) << endl;
			//输出选或不选根节点的最大值
			return 0; //可以结束了
		}
	}

	return 0;
}