Ural 大学有 N 名职员，编号为 1∼N。

他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。

每个职员有一个快乐指数，用整数 Hi 给出，其中 1≤i≤N。

现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。

在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值

思路：

核心：

f[u][0]表示以u为根的子树来选择的方案，并且不选点u

f[u][1]表示以u为根的子树来选择，选点u

代码：

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

const int N = 6000;
int h[N],e[N],ne[N],idx;
int n;
int f[N][2],s[N];
bool has_father[N];

void add(int a,int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}
void dfs(int x)
{
    f[x][1] = s[x];
    for(int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        dfs(j);

        f[x][0] += max(f[j][0],f[j][1]);
        f[x][1] += f[j][0];
    }
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n ; i++ ) cin >> s[i];
    memset(h,-1,sizeof h);

    for(int i = 0; i < n - 1; i ++)
    {
        int a,b;
        cin >> a >> b;
        has_father[a] = true;
        add(b,a);
    }

    int root = 1;
    while(has_father[root]) root ++;

    dfs(root);

    cout << max(f[root][0],f[root][1]) << endl;
    return 0;
}