P1352
题目描述
某大学有 n 个职员，编号为1…n。
他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。
现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 ri，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。
所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。
这题不多做解释，都在代码里了
#include<bits/stdc++.h>
using namespace std;
const int maxn=6005;
int n,f[maxn][2],g[maxn]={0},h[maxn];
vector<int> son[maxn];//动态数组
inline int read()
{
int x=1,y=0;
char z=getchar();
while(z<'0'||z>'9')
{
if(z=='-')
x=-1;
z=getchar();
}
while(z>='0'&&z<='9')
{
y=y*10+z-'0';
z=getchar();
}
return x*y;
}//快读代码
void dp(int x)
{
f[x][0]=0;//如果x不去，那么快乐值为0
f[x][1]=h[x];//如果x去，那么快乐值为h[x]
for(int i=0;i<son[x].size();i++)
{
int y=son[x][i];//y为x的下属
dp(y);//继续查，直到查到它没有下属为止（即该职员没有下属）
f[x][0]+=max(f[y][0],f[y][1]);//如果x不去，那么快乐值就加上他的下属去或不去中的最大值
f[x][1]+=f[y][0];//如果x去，那么快乐值就加上他的下属不去的快乐值
}
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
h[i]=read();
for(int i=1;i<=n-1;i++)
{
int x,y;
x=read();
y=read();
son[y].push_back(x);//son存y的下属，即x
g[x]=1;//如果x有下属，g[x]就存1，否则g[x]存的就是零，即x为最大的上司，他没有上司了
}
int root;
for(int i=1;i<=n;i++)
if(!g[i])
{
root=i;//root存最大上司的编号
break;//查到了就退出
}
dp(root);//从最大上司开始查
cout<<max(f[root][0],f[root][1]);//输出x去和x不去中快乐值较大的那个，就是最终答案
return 0;
}