ZROI-8-06

树形DP和状压DP

状压DP

DP使用状态压缩作为DP状态。
状态压缩动态规划，俗称的状压DP，是利用计算机 二 进制的性质来描述状态的一种DP方式。

很多棋盘问题都运用到了状压，同时，状压也很经常和BFS及DP连用。

状压dp其实就是将状态压缩成进制来保存,其特征就是看起来有点像搜索，每个格子的状态只有1或0 ，是一类非常典型的动态规划。

例题：
P1896 [SCOI2005]互不侵犯)
实际上状压 dp 就是采用位运算，来记录更多的必须记录的状态来做的dp

考虑到每行每列之间都有互相的约束关系。因此，我们可以用行和列作为另一个状态的部分。用一个新的方法表示行和列的状态：数字。考虑任何一个十进制数都可以转化成一个二进制数，而一行的状态就可以表示成这样——例如：$(1010)_2$

就表示：这一行的第一个格子没有国王，第二个格子放了国王，第三个格子没有放国王，第四个格子放了国王。而这个二进制下的数就可以转化成十进制： $(10)_{10}$

于是，我们的三个状态就有了：第几行（用$i$表示）、此行放什么状态（用$j$表示）、包括这一行已经使用了的国王数（用$s$表示）。

考虑状态转移方程。我们预先处理出每一个状态$s[x]$其中包含二进制下1的个数，及此状态下这一行放的国王个数$num[x]$，于是就有：

$f[i][j][s]=sum(f[i−1][k][s−num[j]])$

f[i][j][s]就表示在只考虑前$i$行时，在前$i$行（包括第$i$行）有且仅有s个国王，且第$i$行国王的情况是编号为$j$的状态时情况的总数。而$k$就代表第$i-1$行的国王情况的状态编号

树形DP

以子树作为DP状态的动态规划

一般dp设计状态时用一个点（子树的根）来表示子树，并且附加一个状态

典型例题：没有上司的舞会(洛谷传送门)

做法:
将上司与下属的关系建成一颗树

设 $dp[u][0]$ 表示 u 没有参加舞会时，整个子树的分配方案，且属性为最大值。
设 $dp[u][1]$ 表示 u 参加了舞会时，整个子树的分配方案，属性为最大值。

由题意可知当 u 参加了舞会时，所有下属必须不参加，因此状态转移时, $dp[u][1]$ 只能被 $dp[v][0]$ 更新

当 u 没有参加舞会，下属可以参加，也可以不参加（注意，参加不一定更优）。
因此 $dp[u][0]$可以被$dp[v][0], dp[v][1]更新$.

转移方程(E为有向)

$dp[u][0] = \sum_{(u,v) \in E} max(dp[v][0], dp[v][1]); \\ dp[u][1] = \sum_{(u,v) \in E} dp[v][0];$

答案即为

$max_{\text{x没有入边}}(dp[x][0], dp[x][1]);$

代码

#include <iostream>
#include <algorithm>
#include <cstring>
const int N = 1e5 + 5;
using namespace std;
struct edge
{
	int to, next;/*v;*/
	/*
		to:指向的点；
		next:表示e[x]的下一条边
		v:这条边上的权值
	*/
}e[N*2];
int cnt, head[N],dp[N][2],n,K,L,a[6666];
int in[6666];
/*
	cnt:现在的边数
	head[x]:表示点x最后一条边的编号
*/
void add(int x, int y/*, int v*/)
{
	e[cnt].to = y;
	e[cnt].next = head[x];//这条边的上一条边的编号
	//e[cnt].v = v;
	head[x] = cnt++;//更新这个点x的最终边的编号
}
void dfs(int n)
{
	dp[n][1] = a[n];
	for (int i = head[n]; i != -1; i = e[i].next)
	{
		int& v = e[i].to;
		dfs(e[i].to);
		dp[n][1] += dp[v][0];
		dp[n][0] = max(dp[n][0] + dp[v][1], dp[n][0] + dp[v][0]);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	memset(head, -1, sizeof(head));//初始化
	
	cin >> n;
	for (int i = 1; i <= n; i++)cin >> a[i];
	for (int i = 1; i < n; i++)
	{
		cin >> L >> K;
		add(K, L);
		in[L]++;
	}
	for(int i = 1;i <= n;i++)
		if (in[i] == 0)
		{ 
			dfs(i); cout << max(dp[i][0], dp[i][1]); break;
		}

}