题目大意：

有n个人，每个人有一个欢乐值，并且这些人有上下属关系，一个人可以是多个人的上属，但一个人只能是另外一个人的下属，这样就形成了一颗树形结构，总老板为根。现在让你在这棵树里选取若干个点，使得这些点的欢乐值最大，并且要求这些点不能有直接的上下属关系。注意欢乐值有可能是负的。

dp建立：

状态：

dp[i]表示以i号结点为根的子树最多能得到多少的欢乐值。

状态转移方程：

以i号结点为根的子树能得到的最大的欢乐值为，“所有以i号节点的儿子为根的子树的欢乐值”和“所有以i号结点的孙子为根的子树的欢乐值+i号结点的欢乐值”中的最大值。

代码：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<vector>
#define maxn 10000

using namespace std;
int happy[maxn];
int n,k;
int la,lb;
int dp[maxn]={0};
bool sure[maxn]={0};
bool boss[maxn]={0};
vector<int>son[maxn];
void addedge(int from,int to)
{
    son[from].push_back(to);
}

int f(int x)
{
    if(sure[x]==1)return dp[x];
    if(son[x].size()==0)
    {
        dp[x]=max(happy[x],0);
        sure[x]=1;
        return dp[x];
    }
    int best=0;
    int best1=happy[x];
    int m=son[x].size();
    for(int i=0;i<m;i++)
    {
        int y=son[x][i];
        int t=f(y);
        best+=t;
        int mm=son[y].size();
        for(int j=0;j<mm;j++)
        {
            int tt=f(son[y][j]);
            best1+=tt;
        }
    }
    sure[x]=1;
    dp[x]=max(max(best,0),best1);
    return dp[x];

}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&happy[i]);
    }
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&la,&lb);//lb是la的上属 
        addedge(lb,la);
        boss[la]=1;
    }
    scanf("%d%d",&la,&lb);
    for(int i=1;i<=n;i++)
    {
        if(boss[i]==0)
        {
            k=i;break;
        }
    }
    //int ans=f(k);
    printf("%d\n",f(k));
    //for(int i=1;i<=n;i++)cout<<dp[i]<<" ";
}