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

思路

树形dp基础题型，dp[i][0]表示i不选中时的最大快乐指数，dp[i][1]表示i选中时的最大快乐指数，
所以我们只要先找到一个根节点，然后向下dfs，dp[root][0]和dp[root][1]的较大值就是答案。
从下往上状态转移，我们先搜索到叶子节点，然后求出父节点的dp[i][0]和dp[i][1]就好了。
规则相当简单：dp[fa][1]只能加dp[son][0]，而dp[fa][0]可以加dp[son][0]和dp[son][1]

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=10005;

struct E{
    int next,to;
}edge[maxn];

int n,l,k,h[maxn],ans=0;
int cnt=0,head[maxn],fa[maxn],dp[maxn][2];

void addedge(int from,int to){
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

void dfs(int node,int pre){
    for(int i=head[node];i;i=edge[i].next){
        int to=edge[i].to;
        if(to==pre) continue;
        dfs(to,node);
        dp[node][0]+=max(dp[to][1],dp[to][0]);
        dp[node][1]+=dp[to][0];
    }    
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=n;i++) scanf("%d",&dp[i][1]);
    for(int i=1;i<n;i++){
        scanf("%d%d",&l,&k);
        addedge(k,l);
        fa[l]=k;
    }
    for(int i=1;i<=n;i++){
        if(fa[i]==i){
            dfs(i,0);
            printf("%d",max(dp[i][1],dp[i][0]));
            return 0;
        }
    }
    return 0;
}