题目传送门

题意：给你一颗n(<=3e3)个点的无向树，再给你一个数m(<=1e5)，再给你n个点的权值a[i](<=1e5)

求对于每个x属于[1,m]，是否存在一个连通子图的权值和正好为x。输出一个长度为m的01串，第i个位置上的数字表示是否存在连通子图的权值和正好为i。

思路：点分治+bitset优化

知识盲区。。。打重现的时候满脑子暴力优化，然后T到结束。。。

考虑枚举每个点，找出包含这个点的所有连通子图的权值（这里需要注意，枚举节点u为根时，往下搜索的每一步都是要包含其父节点的答案状态，用bitset存，第i位为1表示存在经过u的连通子图的权值和正好为i）。

这样直接搜是O(n^2)的，再乘上m(?)可能要爆炸。

考虑用分治优化到nlogn。

每次寻找树的重心，并枚举重心往下搜索。

注意初始化。

代码：

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define mst(head,x,n) memset(head+1,x,n*sizeof(head[0]))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dep(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int maxn=3e3+5;
const int maxm=2e5+5;
//const double pi=acos(-1.0);
//const double eps=1e-9;
//const ll mo=1e9+7;
int n,m,k;
int a[maxn],c[maxn];
int tmp,cnt,rt;
int flag;
int sz[maxn];
bool ok[maxn];
vector<int>vc[maxn];
bitset<100010>ans,zt[maxn];
template <typename T>
inline void read(T &X){X=0;int w=0; char ch=0;while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();if(w) X=-X;
}
void dfs(int u,int fa,int n){sz[u]=1;c[u]=0;for(int i=0;i<vc[u].size();i++){int v=vc[u][i];if(v==fa||ok[v]) continue;dfs(v,u,n);sz[u]+=sz[v];c[u]=max(c[u],sz[v]);}c[u]=max(c[u],n-c[u]);if(c[u]<c[rt]) rt=u;
}
void getdp(int u,int fa){sz[u]=1;zt[u]<<=a[u];for(int i=0;i<vc[u].size();i++){int v=vc[u][i];if(v==fa||ok[v]) continue;zt[v]=zt[u];getdp(v,u);zt[u]|=zt[v];sz[u]+=sz[v];}
}
void solve(int u){zt[u].reset();zt[u][0]=1;ok[u]=true;getdp(u,-1);ans|=zt[u];for(int i=0;i<vc[u].size();i++){int v=vc[u][i];if(ok[v]) continue;rt=0;dfs(v,-1,sz[v]);solve(rt);}
}
int main(){#ifdef ONLINE_JUDGE
#elsefreopen("D:/Temp/in.txt", "r", stdin);
#endifint T,cas=1;read(T);while(T--){read(n);read(m);ans.reset();rep(i,1,n) {vc[i].clear();ok[i]=false;}rep(i,1,n-1){int u,v;read(u);read(v);vc[u].push_back(v);vc[v].push_back(u);}rep(i,1,n) read(a[i]);rt=0;c[rt]=inf;dfs(1,-1,n);//cout<<"&^%"<<rt<<endl;solve(rt);rep(i,1,m)printf("%d",(int)ans[i]);puts("");}return 0;
}