有一个大学的庆典晚会，想邀请一些在大学任职的人来參加，每一个人有自己的搞笑值，可是如今遇到一个问题就是假设两个人之间有直接的上下级关系，那么他们中仅仅能有一个来參加，求请来一部分人之后，搞笑值的最大是多少。

树形DP入门题。

DP部分：

dp[i][0]表示职员i不来參加party，以i为根的子树的最大搞笑值，

dp[i][1]表示职员i来參加party。以i为根的子树的最大搞笑值。

转移方程：

dp[cur][1]+=dp[next][0];

dp[cur][0]+=Max(dp[next][1],dp[next][0]);

#include "stdio.h"

#include "string.h"

#include "vector"

using namespace std;

struct node

{

    int fa;

    vector<int>child;

}data[6010];

int dp[6010][2],vis[6010];

int Max(int a,int b)

{

    if (a<b) return b;else return a;

}

void dfs(int cur)

{

    int i,next;

    vis[cur]=1;

    for (i=0;i<data[cur].child.size();i++)

    {

        next=data[cur].child[i];

        if (vis[next]==0)

        dfs(next);

        dp[cur][1]+=dp[next][0];

        dp[cur][0]+=Max(dp[next][1],dp[next][0]);

    }

}

int main()

{

    int n,i,a,b;

    while (scanf("%d",&n)!=EOF)

    {

        memset(dp,0,sizeof(dp));

        memset(data,0,sizeof(data));

        memset(vis,0,sizeof(vis));

        for (i=1;i<=n;i++)

            scanf("%d",&dp[i][1]);

        while(scanf("%d%d",&a,&b))

        {

            if (a+b==0) break;

            data[a].fa=b;

            data[b].child.push_back(a);

        }

        for (i=1;i<=n;i++)

            if (data[i].fa==0)

            {

                dfs(i);

                break;

            }

        printf("%d\n",Max(dp[i][1],dp[i][0]));

    }

    return 0;

}