有一颗苹果树，每个节点上面有很多苹果，从一个节点到另外一个可以到达的节点花费1步，求k步最多能吃到多少苹果，起始点为1，可以不回到起始点。

这是典型的回溯型树状dp。

dp[i][j][0]代表以i为根节点的子树最多j步后回到i能吃到的最多的苹果，

dp[i][j][1]代表以i为根节点的子树最多j步后不回到i节点最多能吃到的子树。那么状态转移就分三步了。

（1）dp[i][j+2][0] = max(dp[i][j+2][0], dp[i][j-k][0]+dp[son][k][0]);

（2）dp[i][j+1][1] = max(dp[i][j+1][1], dp[i][j-k][0]+dp[son][k][1]); 人留在i的子节点son的子树中

（3）dp[i][j+2][1] = max(dp[i][j+2][1], dp[i][j-k][1]+dp[son][k][0]); 人留在不是son的i的子节点的子树中

#include "stdio.h"
#include "string.h"
#include "vector"
using namespace std;

vector< vector
  
    >data(110);
int dp[110][210][3],vis[110],v[110];
int n,m;

int Max(int a,int b)
{
    if (a
   
    =0;j--) for (k=0;k<=j;k++) { dp[cur][j+2][0]=Max(dp[cur][j+2][0],dp[cur][j-k][0]+dp[next][k][0]); dp[cur][j+1][1]=Max(dp[cur][j+1][1],dp[cur][j-k][0]+dp[next][k][1]); dp[cur][j+2][1]=Max(dp[cur][j+2][1],dp[cur][j-k][1]+dp[next][k][0]); } } } } int main() { int i,x,y; while (scanf("%d%d",&n,&m)!=EOF) { for (i=1;i<=n;i++) { data[i].clear(); scanf("%d",&v[i]); } for (i=2;i<=n;i++) { scanf("%d%d",&x,&y); data[x].push_back(y); data[y].push_back(x); } memset(vis,0,sizeof(vis)); memset(dp,0,sizeof(dp)); dfs(1); printf("%d\n",dp[1][m][1]); } return 0; }