没有上司的舞会

有个公司要举行一场晚会。为了让到会的每个人不受他的直接上司约束而能玩得开心，公司领导决定：如果邀请了某个人，那么一定不会再邀请他的直接的上司，但该人的上司的上司，上司的上司的上司……都可以邀请。已知每个人最多有唯一的一个上司。
已知公司的每个人参加晚会都能为晚会增添一些气氛，求一个邀请方案，使气氛值的和最大。

输入描述:

第1行一个整数N表示公司的人数，。
接下一行N个整数。第i行的数表示第i个人的气氛值x，。
接N-1下来每行两个整数K，L。表示第K个人是第L个人的上司。

输出描述:

一个数，表示最大的气氛值和。

示例1
输入

4
1 7 3 4
1 2
2 3
2 4

输出

8

说明

你可以认为公司只有唯一的总boss，这个公司的关系图是一棵树。

wuhui.cppview raw

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int N = 200010;
int a[N];
int n;
vector<int> edge[N];
int cnt[N];
int dp[N][2];

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

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &dp[i][1]);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        edge[a].push_back(b);
        cnt[b]++;
    }
    int t = 0;
    for (int i = 1; i <=n; i++)
        if (!cnt[i]) {
            t = i;
            break;
        }
    dfs(t);
    printf("%d\n", max(dp[t][0], dp[t][1]));
    return 0;
}