树形DP

基本介绍

树形dp顾名思义就是在“树”上进行动态规划，通过遍历树等一些操作来完成题目要求。

在树形动态规划中是建立在树上的，由树中的父节点和子节点的关系推出来的。

一般有两种。

1、就是由子节点推到父节点，即根的子节点传递有用的信息给父节点，最终有父节点再求出最优解。（此形式较为常用）

2、从父节点推至子节点，这种情况的意思是需要取所有点来求出父节点的值，再减去要除的子节点的dp状态，再将其转移，这样就可由根节点推至叶节点。

通常使用链式前向星来建树。

实现形式

树形dp与其他的dp存在一些区别。

他没有固定的形式，很多时候会与其他的算法结合，像背包等等。

与其说是一种算法，说是一种思想更加恰当。

因为自己也不是很理解，也就不详细讲了。。

以后慢慢学习吧，还有很长的路要走。

那这里贴一下链式前向星模板。

const int N = 6060;
int head[N],cnt,in[N];//head数组通常初始化为-1，可以用in数组来求一棵树的根节点

struct {
	int to, val, next;
}Map[N];

void build(int u,int v,int val) {
	Map[++cnt].to = v;
    Map[cnt].val = val;
	Map[cnt].next = head[u];
	head[u] = cnt;
}

典型例题

题目大意

在公司中，老板和员工构成了一个树形结构，每个人有自己的开心值，有一天举办了一个聚会，但是每个人很讨厌和自己的上司一起去，所以上司去他就不会去。问公司最大开心值。

解题思路

先用链式前向星构树。

我们可以用$dp[i][0]$来表示，以i为根节点的子树中，i不去的最大开心值。

$dp[i][1]$来表示，以i为根节点的子树中，i去的最大开心值。

可以得出状态转移方程。

设i的某一个子节点为x。

$dp[i][0] += max(dp[x][0],dp[x][1])$。

$dp[i][1] += dp[x][0]$。

最后答案为$max(dp[root][0],dp[root][1])$。

完整代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 6060;
int head[N],cnt,dp[N][3],h[N],in[N];
struct {
	int to, next;
}Map[N];

void build(int u,int v) {
	Map[++cnt].to = v;
	Map[cnt].next = head[u];
	head[u] = cnt;
}

void dfs(int p) {
	dp[p][0] = 0, dp[p][1] = h[p];
	for (int i = head[p]; ~i; i = Map[i].next) {
		int x = Map[i].to;
		dfs(x);
		dp[p][0] += max(dp[x][0], dp[x][1]);
		dp[p][1] += dp[x][0];
	}
}

int main() {
	int n;
	while (cin >> n) {
		cnt = 0;
		memset(Map, 0, sizeof(Map));
		memset(head, -1, sizeof(head));
		memset(in, 0, sizeof(in));
		for (int i = 1; i <= n; i++) cin >> h[i];
		int l, k;
		while (cin >> l >> k && l || k) {
			build(k, l);
			in[l]++;
		}
		int root = 0;
		for (int i = 1; i <= n; i++) {
			if (!in[i]) {
				root = i;
				break;
			}
		}
		dfs(root);
		cout << max(dp[root][1], dp[root][0]) << endl;
	}
}