题解 | #没有上司的舞会#

思路：

• 用连接表的方式存储图
• 找到根节点，即最高上司，bd[N]表示有父节点，默认为false
• 树形DP：每个人有两种选择，去或者不去舞会，用f[N][2]来存储，f[n][1]表示标号为n的人去舞会，最大的开心值；f[n][0]表示标号为n的人不去舞会，最大的开心值。依次递归处理其子节点。最后根节点的max(f[root][1],f[root][0])即为所求值

#include<bits/stdc++.h>
using namespace std;
const int N=6010;
int happy[N];
bool bd[N];
int e[N],ne[N],h[N],idx=0;
int f[N][2];
void add(int a,int b){
    ne[idx]=h[a],e[idx]=b,h[a]=idx++;
}
void dfs(int u){
    f[u][1]=happy[u];
    for(int i=h[u];i!=-1;i=ne[i]){
        int k=e[i];
        dfs(k);
        f[u][0]+=max(f[k][1],f[k][0]);
        f[u][1]+=f[k][0];
    }
}
int main(){
    memset(h,-1,sizeof(h));
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&happy[i]);
    }
    int a,b;
    while(cin>>a>>b,a,b){
        add(b,a);
        bd[a]=true;
    }
    int root=1;
    while(bd[root]) root++;
    dfs(root);
    cout<<max(f[root][1],f[root][0]);
    return 0;
}