Ural周立大学的校长正在筹备学校的80周年纪念聚会。由于学校的职员有不同的职务级别，可以构成一棵以校长为根的人事关系树。每个职员都有一个唯一的整数编号（范围在1到N之间），并且对应一个参加聚会所获得的欢乐度。为了使每个参加聚会者都感到欢乐，校长想设法使每个职员和他（她）的直接上司不会同时参加聚会。
你的任务是设计一份参加聚会者的名单，使总的欢乐度最高。
输入:
第一行是一个整数N，1<= N <= 6000
以下的N行是对应的N个职员的欢乐度（欢乐度是一个从-128到127之间的整数）
接着是学校的人事关系树，树的每一行格式如下：<L> <K>
表示第K个职员是第L个职员的直接上司。
输入以0 0表示结束
输出：
参加聚会者获得的最大总欢乐度
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
分析：
F[0][i]表示不邀请i的上司的最大欢乐度。 F[1][i]表示邀请i的上司的最大欢乐度。
状态方程：F[0][i]+=F[1][i的职员];
F[1][i]+=max(F[1][i的职员],F[0][i的职员]);
answer=max(F[0][root],F[1][root]);
【参考程序】：
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
int F[2][6010],now[6010],next[6010],child[6010];
int n,root;
int Max(int a,int b)
{
return a>b?a:b;
}
void tree_dp(int k)
{
while (now[k])
{
tree_dp(child[now[k]]);
F[0][k]+=F[1][child[now[k]]];
F[1][k]+=Max(F[1][child[now[k]]],F[0][child[now[k]]]);
now[k]=next[now[k]];
}
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d",&F[0][i]);
now[i]=next[i]=child[i]=0;
}
root=(n+1)*n/2;
int k,l;
for (int i=1;i<=n-1;i++)
{
scanf("%d%d",&l,&k);
next[i]=now[k]; now[k]=i;
child[i]=l; root-=l;
}
tree_dp(root);
printf("%d\n",Max(F[0][root],F[1][root]));
return 0;
}
【参考程序】：
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
int F[2][6010],father[6010];
bool vis[6010];
int n,root;
int Max(int a,int b)
{
return a>b?a:b;
}
void tree_dp(int k)
{
vis[k]=true;
for (int i=1;i<=n;i++)
if (!vis[i] && father[i]==k)
{
tree_dp(i);
F[0][k]+=F[1][i];
F[1][k]+=Max(F[1][i],F[0][i]);
}
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d",&F[0][i]);
father[i]=0;
}
root=0; bool bk=true;
int l,k;
while (scanf("%d%d",&l,&k),l+k>0)
{
father[l]=k;
if (root==l || bk)
{
root=k; bk=false;
}
}
memset(vis,false,sizeof(vis));
tree_dp(root);
printf("%d\n",Max(F[0][root],F[1][root]));
return 0;
}