动态规划：树形DP

动态规划：树形DP"/>

动态规划：树形DP

 没有上司的舞会：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;const int N = 6010;int n;
int happy[N]; //每个职工的高兴度
int f[N][2]; //N1表示选这个点，N2表示不选这个点
int e[N],ne[N],h[N],idx; //邻接表，用来模拟建一个树
bool has_father[N]; //判断当前节点是否有父节点void add(int a,int b)//把a插入树中，头插法，让上司为表头.该表都是他的直系下属
{ //头插法//如图 如1与2之间要有一条线，让2的ne为1，再让h[1]为2的索引。//这样h[1]就是1节点存的最后一个相连的点，如图就是7节点。//而在索引表内部，通过头插法的方式(即每次ne指向上一个点(h存的就是上一个点))，索引表为：7->4->2e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}void dfs(int u)//开始求解题目
{ f[u][1] = happy[u]; //如果选当前节点u，就可以把f[u,1]先怼上他的高兴度for(int i = h[u];i!=-1;i = ne[i])//枚举所有直系下属{ int j = e[i];dfs(j); //找这个下属作为上司的直系下属，计算j的最大高兴度//状态转移方程，不选u，则最大值为不选j和选j的最大值+u。选u，则最大值为不选j + uf[u][0] += max(f[j][1],f[j][0]);f[u][1] += f[j][0];}
}int main()
{scanf("%d",&n);for(int i = 1;i <= n;i ++) scanf("%d",&happy[i]); //输入每个人的高兴度memset(h,-1,sizeof h); //把h都赋值为-1，即邻接表的表头赋-1for(int i = 1;i < n;i ++)//输入节点{int a,b; //对应题目中的L,K,表示b是a的上司scanf("%d%d",&a,&b); //输入has_father[a] = true; //说明a他有上司add(b,a); //把a加入到b的后面}int root = 1; //用来找根节点while(has_father[root]) root ++; //找根节点，直到没有父节点，即它本身就是根节点dfs(root); //从根节点开始搜索printf("%d\n",max(f[root][0],f[root][1])); //输出不选根节点与选根节点的最大值，即选不选校长return 0;
}