题意：

解法：

一开始肯定考虑树形dp,
任取一个点作为根,令d[x][i]表示x的子树是否可以组合成i,
复杂度O(n* m^2),bitset优化的话也还是要O(n* m^2 /64),
主要问题在于dp[v]合并到dp[x]上每次需要O(m),没什么办法优化.可以考虑不进行背包dp[v]和背包dp[x]的合并,
而是用点a[v]和背包dp[x]合并,
这样有点像求数链的背包数组,
但是如果我们回溯点v的时候不删除a[v]的贡献,
那么就变成求连通块的背包数组了,
这样的计算方法需要固定一个点x,
这个点x必须选使得连通块不断开,
可以用点分治做,因为点分治过程中重心是必选的..

code：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxm=3e3+5;
bitset<100005>d[maxm],ans;
vector<int>g[maxm];
int sz[maxm],son[maxm];
int mark[maxm];
int size,root;
int a[maxm];
int n,m;
void getroot(int x,int fa){sz[x]=1;son[x]=0;for(int v:g[x]){if(v==fa||mark[v])continue;getroot(v,x);sz[x]+=sz[v];son[x]=max(son[x],sz[v]);}son[x]=max(son[x],size-sz[x]);if(son[root]>son[x]){root=x;}
}
void dp(int x,int fa){for(int v:g[x]){if(v==fa||mark[v])continue;d[v]=(d[x]<<a[v]);dp(v,x);d[x]|=d[v];}
}
void divide(int x){mark[x]=1;d[x].reset();d[x][a[x]]=1;dp(x,-1);ans|=d[x];for(int v:g[x]){if(mark[v])continue;son[root=0]=size=sz[v];getroot(v,-1);divide(root);}
}
void solve(){cin>>n>>m;for(int i=1;i<=n;i++)g[i].clear();for(int i=1;i<=n;i++)mark[i]=0;ans.reset();for(int i=1;i<n;i++){int a,b;cin>>a>>b;g[a].push_back(b);g[b].push_back(a);}for(int i=1;i<=n;i++)cin>>a[i];son[root=0]=size=n;getroot(1,-1);divide(root);for(int i=1;i<=m;i++){cout<<ans[i];}cout<<endl;
}
signed main(){ios::sync_with_stdio(0);int T;cin>>T;while(T--){solve();}return 0;
}

---