题意是给出一棵树，每个点都有一个权值，从1开始，最多走k步，问能够经过的所有的点的权值和最大是多少（每个点的权值只能被累加一次）。

　　考虑到一个点可以经过多次，设dp状态为dp[i][j][k]，i表示当前从i出发，j表示最多走j步，k=0的话表示最后回到i点，否则不回到i点的子问题的答案。

　　转移见代码。

　　值得注意的是dfs中j循环的方向必须从大到小，因为如果从小到大，当前的j是从比其小的dp[u][j-t][...]更新过来的，而后者是根据走了v以后的更新过来的。换言之，如果从小到大，那么，走v贡献的权值就会被计算多次了，而题目中给的条件是，一个点的权值只能计算一次。拓展一下的话，如果一个点的权值可以被计算多次，那么应当从小到大循环j。

　　不妨以下面这组数据为例可以找到区别：

　　3 3

　　1 100 1

　　1 2

　　1 3

　　代码如下：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6 const int N = 100 + 5; 7  8 int n,k; 9 int val[N];10 vector
         
           G[N];11 int dp[N][N*2][2]; // 0 表示回到原地12 void update(int & a,int b) {
   if(a < b) a = b;}13 int dfs(int u,int fa)14 {15     for(int i=0;i
          
           =1;j--)22 {23 for(int t=1;t<=j;t++)24 {25 // 最终都回到原地，那么左右都需要回到原地，此时需要多走两步 u->v & v->u26 if(t >= 2) update(dp[u][j][0], dp[u][j-t][0] + dp[v][t-2][0]);27 // 最终不用回到原地，有只要左边或者右边一种选择不用回到原地即可28 if(t >= 2) update(dp[u][j][1], dp[u][j-t][1] + dp[v][t-2][0]);29 update(dp[u][j][1], dp[u][j-t][0] + dp[v][t-1][1]);30 }31 }32 }33 }34 35 int main()36 {37 while(scanf("%d%d",&n,&k) == 2)38 {39 memset(dp,0,sizeof dp);40 for(int i=1;i<=n;i++)41 {42 G[i].clear();43 scanf("%d",val+i);44 for(int j=0;j<=k;j++) dp[i][j][0] = dp[i][j][1] = val[i];45 }46 for(int i=1;i