算法题：没有上司的舞会

问题描述

Ural大学有N名职员，编号为1∼N。他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。每个职员有一个快乐指数，用整数 Hi 给出，其中 1≤i≤N。现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

输入格式

第一行一个整数N。(1≤N≤6000)
接下来N行，第i+1行表示i号职员的快乐指数H~i~。(−128≤Hi≤127)
接下来N−1行，每行输入一对整数L,K。表示K是L的直接上司。
最后一行输入0,0。

输出格式

输出最大的快乐指数

样例

输入

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0

输出

5

解决方案

思路

树形动态规划

代码

#include <iostream>
#include <vector>

using namespace std;

int dp[6005][2];
int n;
vector<int> son[6005];
int happy[6005];
int fa[6005];

void dfs(int x) {
    dp[x][0] = 0;
    dp[x][1] = happy[x];

    for (int i = 0; i < son[x].size(); ++i) {
        int y = son[x][i];
        dfs(y);
        dp[x][0] += max(dp[y][0], dp[y][1]);
        dp[x][1] += dp[y][0];
    }

}

int main() {

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> happy[i];
    }

    for (int i = 1; i <= n - 1; ++i) {
        int l, k;
        cin >> l >> k;
        son[k].push_back(l);
        fa[l] = 1;
    }

    int z;
    cin >> z >> z;

    //找根
    int root = 0;
    for (int i = 1; i <= n; ++i) {
        if (!fa[i]) {
            root = i;
            break;
        }
    }

    dfs(root);

    cout << max(dp[root][0], dp[root][1]);

    return 0;
}