没有上司的晚会

Time Limit:10000MS Memory Limit:65536K
Total Submit:117 Accepted:86
Case Time Limit:1000MS

Description

Ural大学有N个职员，编号为1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起与会。

Input

第一行一个整数N。(1<=N<=6000)
接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127)
接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。
最后一行输入0,0。

Output

输出最大的快乐指数。

Sample Input

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0

Sample Output

5

思路

题目大意就是一位职员不能和自己的上司，但是可以和上司的上司，上司的上司的上司 ··· 吃饭
即不能和父结点吃饭，但是可以和“爷”结点，“曾祖父”结点，“曾曾祖父”结点 **···**吃饭。
设计一个参会方案，使快乐指数最大。

所以需要邻接表：

	cin>>e[i].y>>e[i].x;
	e[i].nt=s[e[i].x];
	s[e[i].x]=i;

对于每一个顶点，开一条链，依次存储以该点为起点的边。
$s[i]$ 储存 $i$ 点对应的链的起始位置。$e[i].nt$储存以$i$为根的另一条链的下表。
状态转移方程 :
$f[d][1]+=f[e[i].y][0]$
$f[d][0]+=max(f[e[i].y][0],f[e[i].y][1])$
$f[d][0]$表示以 d 结点为根的子树的最大快乐值 ———且不选 d 结点
$f[d][1]$表示以 d 结点为根的子树的最大快乐值 ———且选 d 结点
那么选 d 则等于子节点不选，不选 d 则等于子节点选或者不选的最大值。

$CODE:$

#include<iostream>
using namespace std;
long long n,a[10001],b[10001],c,s[10001],f[10001][2],p;
struct bos{
	int x;
	int y;
	int nt;
}e[10001];
void in(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}for(int i=1;i<n;i++){
		cin>>e[i].y>>e[i].x;
		b[e[i].y]=1;
		
		//邻接表
		e[i].nt=s[e[i].x];
		s[e[i].x]=i;
	}cin>>p>>p;//输入结尾的0
	
	//下面的for用来寻找根
	for(int i=1;i<=n;i++){
		if(b[i]==0){
			c=i;
		}
	}
}void dp(int d){
	f[d][1]=a[d];
	int i=s[d];
	while(i>0){
		dp(e[i].y);
		f[d][1]+=f[e[i].y][0];//若选d则子节点不选
		f[d][0]+=max(f[e[i].y][0],f[e[i].y][1]);//不选 d 则子节点选或者不选的最大值
		i=e[i].nt;
	}
}
int main(){
	in();
	dp(c);
	cout<<max(f[c][0],f[c][1]);
}