树上的动态规划，即树形DP。做树形DP一般步骤是先将树转换为有根树，然后在树上进行深搜操作，从子节点或子树中返回信息层层往上更新至根节点。

例题1.星象仪

【问题描述】
在寂寞的夜里，星象仪是非常浪漫的东西。但是，你作为一个精神稍微有点不太正常的Geek，把原本正常的星象仪改造得像电报发送器一样。当然，你这个的构造还要更加奇葩一点。具体来说，你的星象仪是一棵满二叉树，二叉树的节点都是有两个输入端和一个输出端的AND 门或者OR 门。它们输入和输出的信号都是只是0 或者1。它们会接受子节点的输出信号，然后将这两个信号进行AND 运算或者OR 运算作为自己的输出。然后，根节点的输出信号就是整个星象仪的输出信号。叶节点的输入信号是由你来调整的，如果二叉树有K 层，那么你显然有2K 个输入信号可以调整。调整一次当然只能改变一个输入信号。根据你的设定，在一开始所有的输入端的输入信号都是0。现在你希望用星象仪得到一串信号，为此，你需要不停地调整输入。

假定你想要用上图中的星象仪得到输出信号000111，一种可行的方案是0001→0011→1100→1111→1010→0101，但是这样你要调整14 次输入信号。更加方便的方式是0000→0000→0000→0101→0101→0101，这样你总计只需要调整2 次输入信号。由于调整输入信号是一件非常麻烦的事情，现在你希望知道对于一台给定的星象仪，如果想要得到一串给定的信号，至少需要调整多少次输入。

【输入格式】
输入文件包含多组测试数据。第一行有一个整数T，表示测试数据的组数。每组测试数据的第一行是一个正整数N，表示输入信号的数目。保证N 是2 的整数次幂。
第二行含有一个由0 和1 组成的字符串S，表示你想要得到的信号。
第三行包含N – 1 个整数，按照层次遍历顺序给出满二叉树的每个节点。整数只会是0 或者1。0 表示二叉树的这个位置是一个OR 门，1 表示是一个AND 门。

【输出格式】
对于每组测试数据，在单独的一行内输出结果。

【样例】
astrology.in

2
4
010101
0 0 0
4
111111
1 1 1

astrology.out

5
4

f[i]表示第i输出得到一个1最少需要几次，先对最后的一层进行预处理，即f[ ]都为1，然后对树从下往上进行搜索，如果是AND门，f[i]=f[i*2]+f[i*2+1]，如果是OR门，则f[i]=min(f[i*2],f[i*2+1])
最后进行判断，具体实现看代码

#include<iostream>
#include<cstdio>
using namespace std;
const int N=20000;
int t,n,la,f[N],b[N],ans,x;
char a[N];
int main()
{
	//freopen("astrology.in","r",stdin);
	//freopen("astrology.out","w",stdout);
	scanf("%d",&t);
	for(int i=1;i<=t;++i)
	{
		ans=0;
		x=0;
		scanf("%d",&n);
		scanf("%s",a+1);
		la=strlen(a+1);
		a[0]='0';
		for(int j=1;j<=n-1;++j)
		{
			scanf("%d",&b[j]);			
		}
		for(int i=n;i<=n*2;++i)
			f[i]=1;
		for(int i=n-1;i>0;--i)
		{
			if(b[i]==1)
			{
				f[i]=f[i*2]+f[i*2+1];
			}
			else
			{
				f[i]=min(f[i*2],f[i*2+1]);
			}
		}
		for(int i=1;i<=la;++i)
		{
			if(a[i]!=a[i-1])
			{
				if(x)
				{
					ans++;	
				}
				else 
				{
					x=1;
					ans+=f[1];
				}							
			}
			
		}
		printf("%d\n",ans);
	}	
	return 0;
}

2.最大子树和

题目大意：在一个无环无向图中（也可以叫树）删去一些边（及边上带的顶点），使剩下的顶点上的值最大。
树形DP。设f[i]为取i这个顶点的美学最大值。F[i]初始都为map[i],则对于所有与i相连的点f[j],如果f[j]>0就加入到f[i]否则不加。注意f[j]不能再遍历i.最后max(f[i])即为所求。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=50000;
int a[N],n,tope,head[N],f[N],in[N],t;
struct node{
	int to,next,w;
}e[N];
int intt(int x,int y,int z)
{
	tope++;
	e[tope].to=y;
	e[tope].next=head[x];
	e[tope].w=z;
	head[x]=tope;
}
inline int sou(int x)
{
	in[x]=1;
	for(int i=head[x];i;i=e[i].next)
	{
		int y=e[i].to;
		if(!in[y])
		{
			t=sou(y);
			if(t>0) f[x]+=t;
		}
	}	
	return f[x];
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		f[i]=a[i];
	}
	for(int i=1;i<=n-1;++i)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		intt(x,y,a[y]);
		intt(y,x,a[x]);
	}
	sou(1);	
	sort(f+1,f+n+1);
	printf("%d",f[n]);
	return 0;
}

3.花花的聚会

4.1 题意描述
花花住在H 国。H 国有n 个城市，其中1 号城市为其首都。城市间有n 􀀀 1 条单向道
路。从任意一个城市出发，都可以沿着这些单向道路一路走到首都。事实上，从任何一个城市
走到首都的路径是唯一的。
过路并不是免费的。想要通过某一条道路，你必须使用一次过路券。H 国一共有m 种过
路券，每张过路券以三个整数表示：v k w：你可以在城市v 以价格w 买到一张过路券。这
张券可以使用k 次。这意味着，拿着这张券通过了k 条道路之后，这张券就不能再使用了。
请注意你同一时间最多只能拥有最多一张过路券。但你可以随时撕掉手中已有的过路券，
并且在所在的城市再买一张。
花花家在首都。他有q 位朋友，他希望把这些朋友们都邀请到他家做客。所以他想要知道
每位朋友要花多少路费。他的朋友们都很聪明，永远都会选择一条花费最少的方式到达首都。
花花需要准备晚餐去了，所以他没有时间亲自计算出朋友们将要花费的路费。你可以帮帮
他么？

4.2 输入格式
输入的第一行包含两个空格隔开的整数n 和m，表示H 国的城市数量和过路券的种数。
之后的n 􀀀 1 行各自包含两个数ai 和bi，代表城市ai 到城市bi 间有一条单向道路。
之后的m 行每行包括三个整数vi; ki 和wi，表示一种过路券。
下一行包含一个整数q，表示花花朋友的数量。
之后的q 行各自包含一个整数，表示花花朋友的所在城市。

4.3 输出格式
输出共q 行，每一行代表一位朋友的路费。

4.4 样例输入
7 7
3 1
2 1
7 6
6 3
5 3
4 3
7 2 3
7 1 1
2 3 5
3 6 2
4 2 4
5 3 10
6 1 20
3
5
6
7

4.5 样例输出
10
22
5

4.6 样例解释
对于第一位朋友，他在5 号城市只能购买一种过路券，花费10 元并且可以使用3 次。这
足够他走到首都，因此总花费是10 元。
对于第二位朋友，他在6 号城市只能购买20 元的过路券，并且只能使用一次。之后，他
可以在3 号城市购买2 元，可以使用3 次的过路券走到首都。总花费是22 元。
对于第三位朋友，他在7 号城市可以购买两种过路券。他可以花3 元买一张可以使用2
次的券，然后在3 号城市再买一张2 元，可以使用3 次的券，走到首都。总花费是5 元，而且
其他的购买方式不会比这种更省钱。

4.7 数据规模与约定
• 对于40% 的数据：n; m; q 10;wi 10；
• 另有20% 的数据：n; m; q 500;wi 100；
• 另有20% 的数据：n; m; q 5000;wi 1000；
• 对于100% 的数据：n; m; q 105;wi 10000; 1 vi; ki n。

花花2333333想到阿花了，阿花可爱多了不是吗╭(╯^╰)╮。
这是一道动态规划，还是一道树形DP，因为题中说明了对于每一个城市只有一条路径到达首都，显而易见就可以建成一个由首都1作为根节点的树。那么记f[u] 为u 跳到根的最少代价。则不难得出转移方程：f[u] = min(f[v]+w[i])，其中v 是u 的祖先，而对于过路券，我们……还是枚举吧，反正可以过[pia]。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
using namespace std;
const int N=200000;
int m,n,tope,head[N],tope1,head1[N],ma,to[N],cnt,ans,f[N];
struct node{
	int lei,w,k,next;
}e[N];
struct node1{
	int to,next;
}t[N];
inline void inttt(int x,int y)
{
	tope1++;
	t[tope1].to=y;
	t[tope1].next=head1[x];
	head1[x]=tope1;
	
}
inline void intt(int x,int k,int w)
{
	tope++;
	e[tope].next=head[x];
	e[tope].k=k;
	e[tope].w=w;
	head[x]=tope;
}
inline void dp(int x)
{
	for(int i=head[x];i;i=e[i].next)//枚举u的过路券 
	{
		int kk=e[i].k,ww=e[i].w;
		cnt=0;
		int a=x;
		while(to[a])
		{
			cnt++;
			a=to[a];
			if(cnt<=kk)
			f[x]=min(f[x],f[a]+ww);		
		}		
	}
}
inline void sou(int x)//从根节点DFS 
{
	for(int i=head1[x];i;i=t[i].next)
	{
		int y=t[i].to;
		dp(y);//更新每一个儿子的f[ ] 
		sou(y);
	}
	return ;
}
int main()
{
	freopen("party.in","r",stdin);
	freopen("party.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n-1;++i)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		to[x]=y;
		inttt(y,x);//建树 
		f[i+1]=999999999;//初始值全为正无穷 
	}
	for(int i=1;i<=m;++i)
	{
		int v1,k1,w1;
		scanf("%d%d%d",&v1,&k1,&w1);
		intt(v1,k1,w1);//记录每一个点的过路券 
	}
	f[1]=0;//根节点 为0 
	sou(1);
	int q;
	scanf("%d",&q);
	for(int i=1;i<=q;++i)
	{
		int x;
		scanf("%d",&x);
		printf("%d\n",f[x]);
	}
	return 0;
}

Criska

动态规划（二）树形DP

例题1.星象仪

2.最大子树和

3.花花的聚会