树形动规总结
树型动规的基本方式同普通的线性动态规划，但遍历的顺序是由高深度向低深度直至根节点，通常一个树型动规包括了状态、阶段、决策、状态转移方程，找到每个题目对应的动归要素，是一个题目的难点所在。
- 状态：程序求解到每个程度所储存的信息，通常我们需要在一开始找到适合题目的状态并进行定义。Tips：找状态可以通过确定变量，权衡变量的范围来寻找。
- 阶段：就是求解动态规划的顺序，每次求解的状态都必须运用之前已经求解过的作为辅助。
- 决策：选择最优解的过程，通常是求最大值，最小值等。
- 状态转移方程：思考出决策后，用状态转移方程将其表达出来。
关于求解顺序：由于树形动归的特殊性（几乎都是无向边），我们应该从叶子节点开始遍历，有三种方法：
- 先给树做一次BFS，然后将队列中的元素一一出队，就是树型动规的顺序。
- 找度为2的节点，记录，并且更新它的子节点的度数，重复这个拓扑排序操作，得到的也是树型动规的顺序。
- 用递归将树的后序遍历求出，即可将一棵树线性化
拓展：状态压缩
当我们的某个状态过于繁琐，很难将其用一个维度表示出来，怎么办？
如山贼集团题目，设立分部的时候各个分部会互相影响，而且不同的分部之间影响的情况是不同的，不像我们通常的动归，所有的物品一视同仁。
比如某结点选择1、2、3分部，会导致总资金损失，而选择1、4分部，总资金却会增加……
观察分部的总数量，小于等于8，这个时候我们可以用到位运算的相关知识，将1~8分部的选择情况用一个int变量储存起来，从而起到表示状态的作用。
Ural 1039没有上司的晚会
背景
有个公司要举行一场晚会。
为了能玩得开心，公司领导决定：如果邀请了某个人，那么一定不会邀请他的上司
（上司的上司，上司的上司的上司……都可以邀请）。
题目
每个参加晚会的人都能为晚会增添一些气氛，求一个邀请方案，使气氛值的和最大。
输入格式
第1行一个整数N（1<=N<=6000）表示公司的人数。
接下来N行每行一个整数。第i行的数表示第i个人的气氛值x(-128<=x<=127)。
接下来每行两个整数L，K。表示第K个人是第L个人的上司。
输入以0 0结束。
输出格式
一个数，最大的气氛值和。
样例输入
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
样例输出
5
提交地址：
http://acm.timus.ru/submit.aspx?space=1&num=1039
首先定义状态：每个结点，然后我们发现在一个人在不参与聚会时，它的相邻子节点可以参加聚会，也可以不参加；一个人参与聚会时，它的相邻子节点一定不能参与聚会。我们加一个状态：参与或者不参与聚会。
dp[i][j]表示第i个人参与(j==1)或不参与(j==0)聚会时聚会所能达到的最大气氛值
#include
#include
#include
using namespace std;
const int MAX=8000;
int w[MAX],f[MAX][2],l,k,rt;
int que[MAX],top,rear,father[MAX];
int first[MAX],nxt[MAX],go[MAX],arcnum;
void addarc(int a,int b){
nxt[++arcnum]=first[a];
first[a]=arcnum;
go[arcnum]=b;
}
int main(){
// freopen("in.txt","r",stdin);
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
while(scanf("%d%d",&l,&k)!=EOF&&l!=0&&k!=0){
father[l]=k;
addarc(k,l);
}
/* for(int i=1;i<=n;i++){
printf("%d ",i);
for(int p=first[i];p!=0;p=nxt[p]){
int j=go[p];
printf("%d ",j);
}
printf("\n");
}printf("\n");*/
for(int i=1;i<=n;i++)
if(!father[i]){
rt=i; break;
}
que[rear++]=rt;
do{
for(int p=first[que[top++]];p!=0;p=nxt[p])
que[rear++]=go[p];
}while(top!=rear);
for(int k=top-1;k>=0;k--){
int i=que[k];
if(first[i]==0){
f[i][0]=0;
f[i][1]=w[i];
}else{
int sum,j;
sum=0;
for(int p=first[i];p!=0;p=nxt[p]){
j=go[p];
sum+=max(f[j][0],f[j][1]);
}
f[i][0]=sum;
sum=0;
for(int p=first[i];p!=0;p=nxt[p]){
j=go[p];
sum+=f[j][0];
}
f[i][1]=sum+w[i];
}
}
printf("%d",max(f[rt][0],f[rt][1]));
/* printf("\n");
for(int i=1;i<=n;i++){
printf("%d %d\n",f[i][0],f[i][1]);
}*/
return 0;
}
