没有上司的舞会

Ural大学有N名职员，编号为1~N。

他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。

每个职员有一个快乐指数，用整数 Hi 给出，其中 1≤i≤N。

现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。

在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

输入格式
第一行一个整数N。

接下来N行，第 i 行表示 i 号职员的快乐指数Hi。

接下来N-1行，每行输入一对整数L, K,表示K是L的直接上司。

最后一行输入0,0。

输出格式
输出最大的快乐指数。

数据范围
1≤N≤6000,
−128≤Hi≤127
输入样例：
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
输出样例：
5

一道简单的树形dp，树形dp嘛，我们一般递归写，每次回溯的时候更新状态，从下而上更新即可找到转移方程。

对于这道题，我们状态状态为 dp[i][j] 表示当前在 i 节点，j 表示去或者不去。

然后呢，状态转移就很简单了，dp[i][0] = sigma ( max ( dp[son][0] , dp[son][1] ) )，这是如果当前的人不去，那么他的下属就可以去了，然后我们在下属去或者不去当中取个最大值即可。
dp[i][1] = sigma ( dp[son][0] ) + h[i] 因为当前这个人去了，那么下属都不能去，然后再加上当前这个人的快乐指数即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=6e3+10;
int n,h[N],k,l,vis[N],dp[N][2];
int head[N],nex[N],to[N],tot;
void add(int a,int b){
	to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
void dfs(int x){
	vis[x]++;
	for(int i=head[x];i;i=nex[i]){
		if(!vis[to[i]]){
			dfs(to[i]);
			dp[x][0]+=max(dp[to[i]][0],dp[to[i]][1]);
			dp[x][1]+=dp[to[i]][0];
		}
	}
	dp[x][1]+=h[x];
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)	cin>>h[i];
	while(cin>>l>>k,k||l)	add(k,l),vis[l]++;
	for(int i=1;i<=n;i++){
		if(vis[i])	continue;
		memset(vis,0,sizeof vis);	dfs(i);
		cout<<max(dp[i][0],dp[i][1])<<endl;	break;
	}
	return 0;
}