本文共 1802 字，大约阅读时间需要 6 分钟。

没有上司的晚会

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]);}