题意：
一颗树，n个点，每个点上有一个权值，求从1出发，最多走k步，遍历到的点的最大权值和。(每个点权对权值和最多只能贡献一次)
先设状态 \(f_{u,i,0/1}\) 表示在 \(u\) 为根节点的子树内从 \(u\) 开始走 \(i\) 步所能得到的最大权值和
0表示在 \(u\) 子树内走完 \(i\) 步后回到 \(u\) 的最大权值和
1表示在 \(u\) 子树内走完 \(i\) 步后不一定回到 \(u\) 的最大权值和
首先，我们考虑 \(f_{u,i,1}\) ，也就是在 \(u\) 子树内走完 \(i\) 步后不一定回到 \(u\) 的最大权值和
那么很显然，它可以先去 \(u\) 的几棵子树里面绕一圈回到 \(u\) ，然后再进入另一棵子树而不一定要回到 \(u\)
这就可以用背包做了，\(v\) 是 \(u\) 的儿子节点
\(f_{u,i,1}=\max\{f_{u,i-(j+1),0}+f_{v,j,1}\}\)
\(f_{v,j+1,1}\) 表示 \(v\) 子树下走 \(j\) 步且不一定回到 \(v\) 的最大权值和
\(f_{u,i-(j+1),0}\) 表示在走 \(v\) 子树前进入其他 \(u\) 的子树走 \(i-(j+1)\) 步并且最后回到 \(u\) 的最大权值和、，要 \(+1\) 的原因是 \(u\rightarrow v\) 也要走一步
当然，既然说了不一定，那我们是不是没考虑
当然， \(f_{u,i,1}\) 还有一种转移
\(f_{u,i,1}=\max\{ f_{u,i-(j+2),1}+f_{v,j,0} \}\)
就是说，我已经确定了一条路线不一定回 \(u\) 了，这时候我在这条路线中间插入一个回 \(u\) 的子树的遍历
比如我原来是遍历完 2 子树回 \(u\)，然后进入 3 子树不一定回来，那我进 3 子树前可以先去 4 子树逛一圈回到 \(u\) 再进 3 子树
\(j+2\) 的原因是 \(u\rightarrow v\) 要走一步，\(v\rightarrow u\) 也要一步
现在来考虑 \(f_{u,i,0}\)，这个思想其实和 \(f_{u,i,1}\) 的第二种转移思想类似
我已经确定了一条路线且回 \(u\) 了，这时候我在这条路线中间插入一个回 \(u\) 的子树的遍历
比如我原来是遍历完 2 子树回 \(u\)，然后进入 3 子树后回 \(u\)，那我进 3 子树前可以先去 4 子树逛一圈回到 \(u\) 再进 3 子树
\(f_{u,i,0}=\max \{ f_{u,i-(j+2),0}+f_{v,j,0} \}\)
那么最后答案就是
\[
ans=\max _{1\le i \le n}\{ f_{i,k,1} \}
\]
转移用背包实现即可，基本的01背包
// This code Write By chtholly_micromaker(MicroMaker)
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define reg register
using namespace std;
const int MaxN=105;
const int MaxK=205;
struct Edge
{
int nxt,to;
}E[MaxN<<1];
template <class t> inline void rd(t &s)
{
s=0;
reg char c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c))
s=(s<<3)+(s<<1)+(c^48),c=getchar();
return;
}
int n,V,en;
int hd[MaxN];
int val[MaxN],f[MaxN][MaxK][2];
inline void adde(int u,int v)
{
++en;
E[en].nxt=hd[u];
E[en].to=v;
hd[u]=en;
return;
}
inline void dfs(int u,int fa)
{
// printf(">>> $ u: %d\n",u);
f[u][0][0]=f[u][0][1]=val[u];
for(int i=hd[u];~i;i=E[i].nxt)
{
reg int v=E[i].to;
if(v==fa)
continue;
dfs(v,u);
for(int j=V;j>=0;--j)
for(int k=0;k<=j;++k)
{
if(k+1<=j)
f[u][j][1]=max(f[u][j][1],f[u][j-(k+1)][0]+f[v][k][1]);
if(k+2<=j)
f[u][j][0]=max(f[u][j][0],f[u][j-(k+2)][0]+f[v][k][0]),
f[u][j][1]=max(f[u][j][1],f[u][j-(k+2)][1]+f[v][k][0]);
}
}
return;
}
inline void work()
{
reg int u,v;
memset(hd,-1,sizeof hd);en=0;
memset(f,0,sizeof f);
for(int i=1;i<=n;++i)
rd(val[i]);
for(int i=1;i<n;++i)
{
rd(u);rd(v);
adde(u,v);
adde(v,u);
}
dfs(1,0);
reg int ans=0;
for(int i=0;i<=V;++i)
ans=max(ans,f[1][i][1]);
printf("%d\n",ans);
return;
}
signed main(void)
{
while(~scanf("%d %d",&n,&V))
work();
return 0;
}