Anniversary party

Description
There is going to be a party to celebrate the 80-th Anniversary of the Ural State University. The University has a hierarchical structure of employees. It means that the supervisor relation forms a tree rooted at the rector V. E. Tretyakov. In order to make the party funny for every one, the rector does not want both an employee and his or her immediate supervisor to be present. The personnel office has evaluated conviviality of each employee, so everyone has some number (rating) attached to him or her. Your task is to make a list of guests with the maximal possible sum of guests’ conviviality ratings.

乌拉尔州立大学成立80周年，将有一个庆祝派对。这所大学有一个等级结构的员工。这意味着主管关系形成了一棵树，植根于教区长诉特列季亚科夫案。为了使每个人的聚会都有趣，校长不希望同时有一名雇员和他或她的直接上司在场。人事办公室已经评估了每个员工的欢乐程度，所以每个人都有一定的数量(等级)附加到他或她身上。你的任务是列出一份宾客名单，尽可能多的列出宾客的欢乐程度。

Input
Employees are numbered from 1 to N. A first line of input contains a number N. 1 <= N <= 6 000. Each of the subsequent N lines contains the conviviality rating of the corresponding employee. Conviviality rating is an integer number in a range from -128 to 127. After that go N – 1 lines that describe a supervisor relation tree. Each line of the tree specification has the form:
L K
It means that the K-th employee is an immediate supervisor of the L-th employee. Input is ended with the line
0 0

雇员从1到 n 被编号。输入的第一行包含一个数字 n。接下来的每个 n 行都包含了相应员工的欢乐度评分。宴会等级是一个从 -128到127的整数。然后是 n-1行，描述一个管理关系树。树的每一行都有这样的格式: l kit 表示 k-th 员工是 l-th 员工的直接主管。输入以0号线结束

Output
Output should contain the maximal sum of guests’ ratings.

输出应该包含客人评分的最大总和。

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

解题思路

这道题和没有上司的舞会完全一样

AC代码

#include<iostream>
using namespace std;
int s,m,x,y,k,f[6005],c[6005][2],head[6005],h[6005];
struct stu//可以用结构体 
{
   
	int x,to,next;
}b[6005];
void add(int x,int y)//链表建立 
{
   
	b[++s].x=x;//他的上司 
	b[s].to=y;//自己 
	b[s].next=head[x];//下一个 
	head[x]=s;//为了方便下一个找自己 
}
void dp(int n)
{
   
	c[n][1]=h[n];//初始值 
	for(int i=head[n];i;i=b[i].next)//翻译为"i=head[n];while(i!=0){执行语句;i=b[i].next;}"就是从头找下去 
	{
   
		dp(b[i].to);//递归到根部 
		c[n][1]=c[n][1]+c[b[i].to][0];//取这个点，他的儿子都不能要 
		c[n][0]=max(c[b[i].to][1],c[b[i].to][0])+c[n][0];//不取这个点，取价值最大的情况 
	}
}
int main()
{
   
	cin>>m;
	for(int i=1;i<=m;i++)
	 cin>>h[i];
	cin>>x>>y;
	while(x!=0||y!=0)
	{
   
		add(y,x);
		f[x]=1;//有上司
		cin>>x>>y;
	} 
	for(int i=1;i<=m;i++)//找到"老大" 
	 if(f[i]==0){
   k=i;break;}
	dp(k);
	cout<<max(c[k][0],c[k][1]);//取或不取中找最大 
}

谢谢