1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
const int kMaxNodes = 110;
vector<vector<int> > edge;
int val[kMaxNodes];
int dp[kMaxNodes][kMaxNodes];
int cntVisit;
//dp(i,j)表示节点i选择j个子节点（包括自己）拥有的最大值
//dp(i,0) = 0 dp(i,1) = val[i];
//遍历自己的子节点
//对每个子节点，计算dp(i,1) 到dp(i,m)
//转移方程
//dp(i,x + y) = max(dp(i,x) + dp(i,y),dp(x,y))
void dfs(int cur,int root) {
    dp[cur][0] = 0;
    dp[cur][1] = val[cur];
    for (int i = 0 ; i < edge[cur].size() ; ++i) {
        int child = edge[cur][i];
        if (child == root)
            continue;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX