HDU 1520 Anniversary party

http://acm.hdu.edu.cn/showproblem.php?pid=1520

题意：

将有一个党庆祝乌拉尔国立大学80周年。大学有一个员工的层次结构。这意味着监督关系形成了一个树根源于校长VE Tretyakov。为了使党对每个人都有趣，主任不想让一个雇员和他或她的直接主管在场。人事局已评估每个员工的欢乐性，所以每个人都有一定数量（评级）附加到他或她。你的任务是制作一个客人的列表，其中有最大可能的客人的欢乐度评分的总和。

思路：

这道题目就是UVa 1220的减弱版，比较基本的树形DP。

d[u][1]代表以u为根的子树中，选u能得到的最大欢乐度。d[u][0]代表不选u能得到的最大欢乐度。

#include<iostream> 
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

int n;
int a[6005];
int d[6005][2];

vector<int> sons[6005];

void dfs(int u)
{
    if (sons[u].size() == 0)
    {
        d[u][1] = a[u];
        d[u][0] = 0;
        return;
    }

    if (d[u][1])   return;

    int k = sons[u].size();
    for (int i = 0; i < k; i++)
    {
        int son = sons[u][i];
        dfs(son);
        d[u][1]+= d[son][0];

        d[u][0]+= max(d[son][1], d[son][0]);
    }
    d[u][1] += a[u];
}

int main()
{
    //freopen("D:\txt.txt", "r", stdin);
    int x, y;
    while (cin >> n)
    {
        memset(d, 0, sizeof(d));
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            sons[i].clear();
        }
        while (cin >> x>> y)
        {
            if (x == 0 && y == 0)  break;
            sons[y].push_back(x);
        }

        int Max = 0;
        for (int i = 1; i <= n; i++)
        {
            dfs(i);
            Max = max(Max, max(d[i][1], d[i][0]));
        }
        cout << Max << endl;
    }
    return 0;
}