动态规划--树形DP

https://www.acwing.com/problem/content/287/

所谓树形DP，也就是关系的两边变成了树的上层和下层。

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 const int N=6010;
 5 int happy[N];
 6 int h[N],e[N],ne[N],idx;
 7 int d[N];
 8 int f[N][2];
 9 void add(int a,int b){
10     e[idx]=b,ne[idx]=h[a],h[a]=idx++;
11 }
12 void dfs(int u){
13     for(int i=h[u];i!=-1;i=ne[i]){
14         int j=e[i];
15         dfs(j);
16         f[u][0]+=max(f[j][0],f[j][1]);
17         f[u][1]+=f[j][0];
18     }
19     f[u][1]+=happy[u];
20 }
21 int main(void){
22     int n;
23     cin>>n;
24     for(int i=1;i<=n;i++) cin>>happy[i];
25     memset(h,-1,sizeof(h));
26     for(int i=0;i<n-1;i++){
27         int a,b;
28         cin>>a>>b;
29         add(b,a);
30         d[a]++;
31     }
32     int root=0;
33     for(int i=1;i<=n;i++)//找到根节点
34         if(d[i]==0)
35             root=i;
36     dfs(root);
37     cout<<max(f[root][0],f[root][1]);
38     return 0;
39 }