洛谷 P1352. 没有上司的舞会

链接

https://www.luogu.com.cn/problem/P1352

题意

一颗带点权的有根树，一个节点不能和其父节点一起选，选择一些节点，求这些节点权值和的最大值

思路

树形DP

不选节点 $i$：$dp[i][0]=\sum_{j \in son(i)}{max(dp[j][0],dp[j][1])}$

选择节点 $i$：$dp[i][1]=h[i]+\sum_{j \in son(i)}{dp[j][0]}$

找到根节点开始 DFS 即可

代码

#include<bits/stdc++.h>
using namespace std;
const int N=6005;
int n,h[N],dp[N][2];
bool st[N];
vector<int>son[N];
void dfs(int u) {
    dp[u][1]=h[u];
    for(auto x:son[u]) {
        dfs(x);
        dp[u][0]+=max(dp[x][0],dp[x][1]);
        dp[u][1]+=dp[x][0];
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i];
    for(int i=1;i<n;i++) {
        int l,k;
        cin>>l>>k;
        st[l]=true;
        son[k].push_back(l);
    }
    for(int i=1;i<=n;i++) if(!st[i]) {dfs(i),cout<<max(dp[i][0],dp[i][1])<<endl;break;}
    return 0;
}