没有上司的舞会

描述

有个公司要举行一场晚会。
为了能玩得开心，公司领导决定：如果邀请了某个人，那么一定不会邀请他的上司
（上司的上司，上司的上司的上司……都可以邀请）。
题目
每个参加晚会的人都能为晚会增添一些气氛，求一个邀请方案，使气氛值的和最大。

输入

第1行一个整数N（1<=N<=6000）表示公司的人数。
接下来N行每行一个整数。第i行的数表示第i个人的气氛值x(-128<=x<=127)。
接下来每行两个整数L，K。表示第K个人是第L个人的上司。
输入以0 0结束。

输出

一个数，最大的气氛值和。

样例

输入

输出

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,head[1000001],tot,a[100001],f[10001][2],fa[100001],root;
 4 struct data {
 5     int to,nxt;
 6 } e[1000001];
 7 void build(int x,int y) {
 8     e[++tot].to=y;
 9     e[tot].nxt=head[x];
10     head[x]=tot;
11 }
12 void dp(int x) {
13     f[x][0]=0;
14     f[x][1]=a[x];
15     for(int i=head[x]; i; i=e[i].nxt) {
16         int v=e[i].to;
17         if(v==x)
18             continue;
19         dp(v);
20         f[x][1]+=f[v][0];
21         f[x][0]+=max(f[v][0],f[v][1]);
22     }
23 }
24 int main() {
25     scanf("%d",&n);
26     for(int i=1; i<=n; i++)
27         scanf("%d",&a[i]);
28     while(1) {
29         int x,y;
30         scanf("%d%d",&x,&y);
31         if(x==0&&y==0)
32             break;
33         build(y,x);
34         fa[x]=1;
35     }
36     for(int i=1; i<=n; i++)
37         if(!fa[i])
38             root=i;
39     dp(root);
40     printf("%d
",f[root][1]>f[root][0]?f[root][1]:f[root][0]);
41     return 0;
42 }