描述 Description
Ural 大学有 N 个职员，编号为 1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起与会。
输入格式 InputFormat
第一行一个整数 N(1<=N<=6000)。
接下来 N 行，第 i+1 行表示 i 号职员的快乐指数 Ri(-128<=Ri<=127)。
接下来 N-1 行，每行输入一对整数 L,K。表示 K 是 L 的直接上司。
最后一行输入 0 0。
输出格式 OutputFormat
输出最大的快乐指数。
样例输入 SampleInput
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
样例输出 SampleOutput
5
注释 Hint
简单的树形动规。从下往上做。
代码 Code
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
struct node
{
int num,dist;
}d[6001];
int a[6001],fa[6001];
int f[6001][2];
int i,j,t,n,m,l,r,k,z,y,x;
bool flag;
void find()
{
int i,j,t;
m=0;d[m].num=r;d[m].dist=0;m++;
j=0;t=0;
while (t>=j)
{
for (i=1;i<=n;i++) if (fa[i]==d[j].num)
{
d[++t].num=i;
d[t].dist=d[j].dist+1;
}
j++;
}
m=t+1;
}
bool comp(node a,node b)
{
return a.dist>b.dist;
}
int main()
{
memset(a,0,sizeof(a));
memset(fa,0,sizeof(fa));
memset(f,0,sizeof(f));
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
for (i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
fa[x]=y;
}
scanf("%d%d",&x,&y);
for (i=1;i<=n;i++) if (fa[i]==0) break;
r=i;
find();
sort(d,d+m,comp);
for (i=0;i<m;i++)
{
x=d[i].num;
flag=false;
for (j=0;j<i;j++)
{
y=d[j].num;
if (fa[y]==x)
{
f[x][0]+=max(f[y][0],f[y][1]);
f[x][1]+=f[y][0];
flag=true;
}
}
f[x][1]+=a[x];
if (!flag)
{
f[x][0]=0;
f[x][1]=a[x];
}
}
printf("%d\n",max(f[r][1],f[r][0]));
return 0;
}