acwing285. 没有上司的舞会

题目

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

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

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

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

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

题解

父节点参会，那么子节点就不能再参会了，所以只需要在两者之间取一个最大值。
f[u][1]表示以u为根节点的职员参会，f[u][0]表示以u为根节点的职员不参会。

节点u参会时，u的子节点j都不能参与，即f[u][1]+=f[j][0]，其中j为u的所有子节点。
节点u不参会时，u的子节点j都能参与或者不参与，取最大值即可。即f[u][0]+=max(f[j][1],f[j][0])，其中j为u的所有子节点。
最后的答案即为根节点的最大值:max(f[root][0],f[root][1])。

#include<iostream>
#include<cstring>
using namespace std;
const int N=6010;

int n,happy[N];
int f[N][2];
bool has_par[N];
int e[N],ne[N],h[N],idx;
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void dfs(int u){
    f[u][1]=happy[u];
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        dfs(j);
        f[u][1]+=f[j][0];
        f[u][0]+=max(f[j][1],f[j][0]);
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>happy[i];
    }
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        add(b,a);
        has_par[a]=true;
    }
    int root=1;
    while(has_par[root])root++;
    dfs(root);
    cout<<max(f[root][0],f[root][1])<<endl;
    
    return 0;
}