题目大概是一棵树，每个结点都有若干个苹果，求从结点1出发最多走k步最多能得到多少个苹果。
考虑到结点可以重复走，容易想到这么个状态：
- dp[u][k][0]表示在以结点u为根的子树中走k步且必须返回u能得到的最多苹果
- dp[u][k][1]表示在以结点u为根的子树中走k步且可以不返回u能得到的最多苹果
- 单纯这样转移又是指数级的时间复杂度，所以又是树上背包了
转移就是：
- dp[u][k][0]=max(dp[u][k][0],dp[v][k'][0]+dp[u][k-k'-2][0])（v是u当前的孩子），对于必须返回的就是从u走一步到v，分k‘个给当前的子树v走并走回v，最后再走一步返回u
- dp[u][k][1]=max(dp[u][k][1],dp[v][k'][1]+dp[u][k-k'-1][0])（v是u当前的孩子），之前的子树走完回到u，走一步到v，最后不返回地在当前的子树v中走k‘步
不过这样提交WA。。然而看不出哪里有错。。无奈看别人代码，发现转移少考虑了一种情况——
- dp[u][k][1]=max(dp[u][k][1],dp[v][k'][0]+dp[u][k-k'-2][1])（v是u当前的孩子），从u走一步到v，分配k'步给当前子树v走并返回v，再走一步回到u，最后不返回地向之前的子树走
真的想不到。。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 111
struct Edge{
int v,next;
}edge[MAXN<<];
int NE,head[MAXN];
void addEdge(int u,int v){
edge[NE].v=v; edge[NE].next=head[u];
head[u]=NE++;
}
int d[MAXN][][];
int n,m,apple[MAXN];
void dp(int u,int fa){
d[u][][]=d[u][][]=apple[u];
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(v==fa) continue;
dp(v,u);
for(int j=m; j>; --j){
for(int k=; k<j; ++k){
if(d[v][k][]==- || d[u][j-k-][]==-) continue;
d[u][j][]=max(d[u][j][],d[v][k][]+d[u][j-k-][]);
}
for(int k=; k<j-; ++k){
if(d[v][k][]==- || d[u][j-k-][]==-) continue;
d[u][j][]=max(d[u][j][],d[v][k][]+d[u][j-k-][]);
}
for(int k=; k<j-; ++k){
if(d[v][k][]==- || d[u][j-k-][]==-) continue;
d[u][j][]=max(d[u][j][],d[v][k][]+d[u][j-k-][]);
}
}
}
}
int main(){
int a,b;
while(~scanf("%d%d",&n,&m)){
NE=;
memset(head,-,sizeof(head));
for(int i=; i<=n; ++i) scanf("%d",apple+i);
for(int i=; i<n; ++i){
scanf("%d%d",&a,&b);
addEdge(a,b); addEdge(b,a);
}
memset(d,-,sizeof(d));
dp(,);
int res=-;
for(int i=; i<=m; ++i){
res=max(res,d[][i][]);
}
printf("%d\n",res);
}
return ;
}