题意：T组样例，给次给出一个N节点的点权树，以及M，问连通块的点权和sum的情况，输出sum=1到M，用0或者1表示。
思路：背包，N^2，由于是无向的连通块，所以可以用分治优化到NlgN。 然后背包可以用bitset优化。注意不要想着背包合并背包，背包只能合并单点。
#include<bits/stdc++.h> #define pb push_back #define rep(i,a,b) for(int i=a;i<=b;i++) #define Gv G[u][i] #define feach(i,u) for(int i=0;i<G[u].size();i++) using namespace std; const int maxn=3010; vector<int>G[maxn]; bitset<100010>s[maxn],ans; int a[maxn],sz[maxn],son[maxn],vis[maxn],rt; void dfs(int u,int f,int n){ sz[u]=1; son[u]=0; feach(i,u){ if(Gv==f||vis[Gv]) continue; dfs(Gv,u,n); sz[u]+=sz[Gv]; son[u]=max(son[u],sz[Gv]); } son[u]=max(son[u],n-son[u]); if(son[u]<son[rt]) rt=u; } void getdp(int u,int f){ sz[u]=1; s[u]<<=a[u]; feach(i,u){ if(Gv==f||vis[Gv]) continue; s[Gv]=s[u]; getdp(Gv,u); sz[u]+=sz[Gv]; s[u]|=s[Gv]; } } void solve(int u){ vis[u]=1; s[u].reset();s[u][0]=1; getdp(u,-1); ans|=s[u]; feach(i,u){ if(!vis[Gv]){ rt=0; dfs(Gv,-1,sz[Gv]); solve(rt); } } } int main() { int T,N,M; scanf("%d",&T); son[0]=4010; while(T--){ scanf("%d%d",&N,&M); rep(i,1,N) G[i].clear(),vis[i]=0; ans.reset(); rep(i,1,N-1){ int u,v; scanf("%d%d",&u,&v); G[u].pb(v); G[v].pb(u); } rep(i,1,N) scanf("%d",&a[i]); rt=0; dfs(1,-1,N); solve(rt); rep(i,1,M) printf("%d",(int)ans[i]); puts(""); } return 0; }