题意:
解法:
一开始肯定考虑树形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;
}