题意：一棵n个点的树，每个点有苹果数vi，每条边长度为1。从树根1出发，你不能走多于m步，走到一个点就能获得该点苹果，问能获得最多苹果是多少个？
解法：这道题想了挺久的还是没想到只能看题解了。很经典的树形DP了。
很容易想到设dp[x][j]表示x子树分配j步能获得最多苹果数量，但是这样是不够的，因为很容易发现只有哪些回到了x点的方案的代价才是子树大小*2，但是走到最后的时候其实可以不用回到x点。那么我们就增加状态纬度，设dp[i][j][0/1]:给树i恰好分配j步(回/不回来)i点的最大值。然后分3中情况写状态转移方程：
因为我们是一边遍历儿子一边做背包，所以在遍历当前y子树的时候，dp[x]可以看成是左边子树结果集，dp[y]就是当前子树结果集，状态转移方程其实就是想办法把这两个结果集结合在一起。那么其实就三种情况：左边回来且现在回来，走边回来走到右边之后不回来了，右边回来走到左边之后不回来了
dp[x][j][0]=max(dp[x][j][0],dp[x][j-k][0]+dp[y][k-2][0]); //情况①：表示遍历从左边的子树回来x点之后，去y子树，再回来x点。
dp[x][j][1]=max(dp[x][j][1],dp[x][j-k][0]+dp[y][k-1][1]); //情况②：表示从左边回来，去y子树，不回来x点了
dp[x][j][1]=max(dp[x][j][1],dp[x][j-k][1]+dp[y][k-2][0]); //情况3：表示从y子树回来，去左边，不回来x点了
写了这三种情况就可以AC了。这里提一个小细节，网上很多代码dp[x][j][0/1]代表的是给x树分配小于等于j步的最大价值，博主写的是恰好分配j步，这点不同在代码会有小小的不同。
总的来说，感觉这道题还是不容易想到，首先得有经验发现状态不够时增加一个[0/1]纬度表示，然后的写出正确的状态转移方程才能写对，也只能多做题才能有感觉吧。
#include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; const int N=1e2+10; int n,m,v[N]; vector<int> G[N]; int dp[N][N<<1][2]; //dp[i][j][0/1]:给树i分配j步(回/不回来)i点的最大值 void dfs(int x,int fa) { for (int i=0;i<G[x].size();i++) { int y=G[x][i]; if (y==fa) continue; dfs(y,x); for (int j=m;j>=0;j--) { //计算dp[x][j] for (int k=1;k<=j;k++) { //给儿子y分配k步 if (k>=2) dp[x][j][0]=max(dp[x][j][0],dp[x][j-k][0]+dp[y][k-2][0]); if (k>=1) dp[x][j][1]=max(dp[x][j][1],dp[x][j-k][0]+dp[y][k-1][1]); if (k>=2) dp[x][j][1]=max(dp[x][j][1],dp[x][j-k][1]+dp[y][k-2][0]); } } } } int main() { while (scanf("%d%d",&n,&m)==2) { for (int i=1;i<=n;i++) G[i].clear(); memset(dp,-0x3f,sizeof(dp)); for (int i=1;i<=n;i++) scanf("%d",&v[i]),dp[i][0][0]=dp[i][0][1]=v[i]; for (int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); G[x].push_back(y); G[y].push_back(x); } dfs(1,0); int ans=0; for (int i=0;i<=m;i++) ans=max(ans,max(dp[1][i][0],dp[1][i][1])); printf("%d\n",ans); } return 0; }