题目链接：

思路：经典的树形dp,想了好久的状态转移。dp[i][j][0]表示从i出发走了j步最后没有回到i，dp[i][j][1]表示从i出发走了j步最后回到i。于是我们把所有到情况归结为3种：

1、从u（v是其中一颗子树）出发，走了j步，最后停在了v,则有dp[u][j+1][0]=max(dp[u][j+1][0],dp[u][j-k][1]+dp[v][k][0]);(从u->v多走了1步).

2、从u出发，走了j步，最后停在了u的另一棵子树上，则有dp[u][j+2][0]=max(dp[u][j+2][0],dp[u][j-k][0]+dp[v][k][1])（从u->v,,v->u多走了2步）.

3、从u出发，走了j步，最后回到u,则有dp[u][j+2][1]=max(dp[u][j+2][1],dp[u][j-k][1]+dp[v][k][1])（从u->v,,v->u多走了2步）.

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 #define MAXN 222 8  9 int n,m,val[MAXN];10 vector
           
            
              >g;11 int dp[MAXN][MAXN][2];12 13 void dfs(int u,int father)14 {15 for(int i=0; i<=m; i++)dp[u][i][0]=dp[u][i][1]=val[u];16 for(int i=0; i
             
              =0; j--) {21 for(int k=0; k<=j; k++) {22 dp[u][j+1][0]=max(dp[u][j+1][0],dp[u][j-k][1]+dp[v][k][0]);23 dp[u][j+2][0]=max(dp[u][j+2][0],dp[u][j-k][0]+dp[v][k][1]);24 dp[u][j+2][1]=max(dp[u][j+2][1],dp[u][j-k][1]+dp[v][k][1]);25 }26 }27 }28 }29 30 int main()31 {32 int _case,u,v;33 while(~scanf("%d%d",&n,&m)) {34 g.clear();35 g.resize(n+2);36 for(int i=1; i<=n; i++)scanf("%d",&val[i]);37 for(int i=1; i