P1352 没有上司的舞会

~~~~~      P1352 没有上司的舞会 ~~~~~      总题单链接

思路

~~~~~      设 $dp[u][[0/1]$ 表示第 $u$ 个点 $[不选/选]$ 的最大值。

~~~~~      $dp[u][1]$ 只能用 $dp[v][0]$ 来更新（$v$ 是 $u$ 的儿子），因为不能同时选一个点和他的儿子。

~~~~~      $dp[u][0]$ 可以用 $dp[v][0]$ 来更新，也可以用 $dp[v][1]$ 来更新。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;vector<ll>eg[6005];
ll n,S,a[6005],din[6005],dp[6006][2];void dfs(ll p){dp[p][1]+=a[p];for(ll v:eg[p]){dfs(v);dp[p][1]+=dp[v][0];dp[p][0]+=max(dp[v][0],dp[v][1]);}
}signed main(){ios::sync_with_stdio(false);cin>>n;for(ll i=1;i<=n;i++)cin>>a[i];for(ll i=1;i<n;i++){ll x,y;cin>>x>>y;eg[y].push_back(x);din[x]++;}for(ll i=1;i<=n;i++)if(!din[i])S=i;dfs(S);cout<<max(dp[S][0],dp[S][1]);return 0;
}