题目在各大OJ都有，就不在多说;
我们设递推数组f[MAXN][2] f[i][1]表示第i个人来时以i为根的子树的最大快乐指数； f[i][0]表示第i个人不来时以i为根的子树的最大快乐指数；代码有详解
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
const int MAXN=10000;
using namespace std;
struct Node
{
int next,to;
}edge[MAXN];
int f[MAXN][2],degree[MAXN],head[MAXN],cnt,n,x,y;
inline void Add_Edge(int u,int v)
{
edge[++cnt].next=head[u];
edge[cnt].to=v;
head[u]=cnt;
}
void Dfs(int u)
{
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
Dfs(v);
f[u][0]+=max(f[v][0],f[v][1]);//若上司不来，则下属可以来f[v][1],也可以不来f[v][0];
f[u][1]+=f[v][0];//若上司来，则下属一定不来f[v][0];
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&f[i][1]);//若上司来则f[i][1]一定包括上司的值，所以直接初始化就好
while(scanf("%d%d",&x,&y)&&x&&y)
{
Add_Edge(y,x);//连边建树
degree[x]++;//记录入度方便寻找根（没有上司的节点）
}
for(int i=1;i<=n;i++)
{
if(!degree[i])//找到根
{
Dfs(i);//DP
printf("%d",max(f[i][0],f[i][1]));//输出
return 0;
}
}
return 0;
}
