/*

f[i][0/1] 0与1分别表示第i个人不去，去时的最大快乐指数

所以 f[i][0] += max（ f[son][1] ,f[son][0]）;

f[i][1] += max(f[son][0] , 0)

1.为什么f[i][1] 要与0 做比较? : 因为快乐指数可能是负的

2. 为什么f[i][0] 不用与0作比较，直接＝max？：就算是负的，也只能直接去最大的，他又不去．．．　

3.为什么是+=？ ： 下面有

*/

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 const int MAXN = 6000+9; 5  6 int n,cnt; 7 int head[MAXN]; 8 int R[MAXN],f[MAXN][2],fa[MAXN];  9 10 struct edge{11     int y,next;12 }e[MAXN];13 14 void add_edge(int x, int y) {15     e[++cnt].y = y;16     e[cnt].next = head[x];17     head[x] = cnt;18 }19 20 void dfs(int now) {21     f[now][1] = R[now];22     f[now][0] = 0;//初始化23     for(int i = head[now]; i; i = e[i].next ) {
   //i是边编号 24         int nn = e[i].y ;25         dfs(nn);//先递归进去处理儿子的f值 26         f[now][0] += max(f[nn][1] ,f[nn][0]) ;27         f[now][1] += max(f[nn][0] , 0);28     //注：因为一棵树可能有多个儿子，所以这里都是+=; 29     }30 }31 32 int main() {33     scanf("%d",&n);34     for(int i = 1; i <= n; i++) {35         scanf("%d",&R[i]);36     }37     int l,k;38     for(int i = 1; i <= n; i++) {39         scanf("%d%d",&l,&k);40         if(i == n) break;//只输入了n-1行 41         fa[l] = k;42         add_edge(k,l);43     }44     int root;45     for(int i = 1; i <= n; i++) if(!fa[i]) {46         root = i;47         break;//找根48     }49     dfs(root);50     int ans = max(f[root][0],f[root][1]);51     printf("%d",ans);52 }
      
     

类似的组题（非常好

注： 因为相当于0-1背包中的选或不选，所以 j 是逆序的，其他细节在代码里有体现和解释

1 #include
     
       2 #include
      
        3 using namespace std; 4 const int MAXN = 100+9; 5  6 int n,Q; 7 int f[MAXN][MAXN];//f[i][j]表示： 点i和它的子树保留j个树枝时的最大苹果数  8 int head[MAXN],cnt; 9 10 struct edge{11     int y,val,next;12 }e[MAXN];13 14 void add_edge(int x, int y, int val) {15     e[++cnt].y = y;16     e[cnt].val = val;17     e[cnt].next = head[x];18     head[x] = cnt;19 } 20 21 void dfs(int now ,int dad) {22     f[now][0] = 0;//初始化边界23     for(int i = head[now]; i; i = e[i].next ) {24         int nn = e[i].y ;25         if(nn == dad) continue ;//应该是continue吧，不是return ； 26         dfs(nn, now);//先递归进去处理儿子的f值 27         for(int j = Q; j; j--) {
   //逆序的原因: 0-1背包选或不选 28             for(int k = 0; k < j; k++) {
   //枚举 左/右 子树保留的树枝29                 f[now][j] = max(f[now][j], f[now][j-k-1] + f[nn][k] + e[i].val );30                                             //要选子树nn上边，就要把子树nn与根的边选上，所以这里是j-k还要"-1" 31             }32         }33     }34 }35 36 int main() {37     scanf("%d%d",&n,&Q);38     int m = n-1;//二叉树的边 39     for(int i = 1, x, y, val; i <= m; i++) {40         scanf("%d%d%d",&x,&y,&val);41         add_edge(x,y,val);42         add_edge(y,x,val);//只是描述了边，但不知道父亲是谁，儿子是谁,所以建双向的43         //所以下面的dfs要开一个树根的形参，防止死循环 44     }45     //1为根46     dfs(1,1);47     printf("%d",f[1][Q]);48     return 0;49 }