题意描述

某大学有$N$个职员，编号为$1~N$。

他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数$R_i$.

但是呢，如果某个职员的上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

所以，请你编程计算，邀请哪些职员可以使快乐指数最大，并求出最大的快乐指数。

输入格式

第一行一个整数$N$。

接下来$N$行，第$i+1$行表示$i$号职员的快乐指数$R_i$。

接下来$N-1$行，每行输入一对整数$L$,$K$。表示$K$是$L$的直接上司。

最后一行输入$0$ $0$

输出格式

输出只有一行，为一个整数$ans$，表示最大的快乐指数。

Input & Output ‘s examples

Input ‘s eg

Output ‘s eg

分析

树形$dp$入门经典

设$f[i][01]$表示第$i$个人来与不来时的最大欢乐值，第二维为$0$表示他不来，$1$表示他来。

如果他来，则他的下属们都不会来，因此我们只需要加上他的欢乐指数。即

$f[i][1] = f[son][0] + r[i]$

如果他不来，则他的下属们可以来也可以不来(因为下属可能也是别人的领导，所以下属全都来并不一定是最好的)。因此我们需要在这之中取一个$Max$，即

$f[i][0] = max(f[son][0] , f[son][1])$

在输入时，开一个数组记录没有上司的那个人，则那个人就是校长，记为$root$。则最后的答案就是$max(f[root][0] , f[root][1])$

是不是很简单啊(逃 ~

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 10001

using namespace std;

struct Edge{
    int to;
    int last;
}edge[N];

int head[N];
int edge_num;

I void add_edge(int from , int to){
    edge[++ edge_num] = Edge{to , head[from]};
    head[from] = edge_num;
}

int n;
int happy[N];
int fa[N];
int f[N][2];

void dp(int x){
    for(int i = head[x] ; i ; i = edge[i].last){
        int to = edge[i].to;
        dp(to);
        f[x][1] += f[to][0];
        f[x][0] += max(f[to][0] , f[to][1]);
    }
    f[x][1] += happy[x];
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> happy[i];
    }
    int u , v;
    for(int i = 1; i <= n - 1; i ++){
        cin >> u >> v;
        fa[u] ++;
        if(u != 0 && v != 0){
            add_edge(v , u);
        }
    }
    int root;
    for(int i = 1; i <= n; i ++){
        if(fa[i] == 0){
            root = i;
            break;
        }
    }
    dp(root);
    cout << max(f[root][1] , f[root][0]) << "\n";
    return 0;
}