這是一道非常好的題,V8強力推薦。。
題目連結:http://acm.hdu.edu.cn/downloads/CCPC2018-Hangzhou-ProblemSet.pdf(pdf不好複制是以就貼連結了。。
一個很顯然的思路是樹上跑背包,然而O(
)絕對是會T的。。
是以直接背包肯定是不行的。。背包的合并代價實在太高了。。
然後萬能的V8告訴窩萌可以借鑒鍊合并的方式來代替背包的工作,即不讓背包和背包合并,而是用鍊和背包合并。。
具體來說,就是邊dfs,邊用dfs周遊到的點的權值和與原背包進行和并,這是不是很像在找直徑的過程中邊維護最長半鍊,邊用目前的半鍊和最長半鍊合并得到直徑呢?
實作上是将目前的背包指派給了子節點,讓他在dfs的過程中拓展,而由于是01背包,用bitset會快很多(看代碼吧實在說不清楚。。
這樣一來會發現一個問題。。這樣求得的聯通塊必定包含根,而對不包含根的聯通塊還要再求。。
直接求的話是O(
)的。。然而如果用點分治就能降到O(nmlogn)了。。由于有bitset的優化和時限開到了8s。。是以還是能過的。。
然後跑的飛快怒拿rk2。。bitset是個好東西啊~~~
這個代替背包合并的姿勢值得學習!!
/**
* ┏┓ ┏┓
* ┏┛┗━━━━━━━┛┗━━━┓
* ┃ ┃
* ┃ ━ ┃
* ┃ > < ┃
* ┃ ┃
* ┃... ⌒ ... ┃
* ┃ ┃
* ┗━┓ ┏━┛
* ┃ ┃ Code is far away from bug with the animal protecting
* ┃ ┃ 神獸保佑,代碼無bug
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┗━━━┓
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━━━━━━━━┳┓┏┛
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define eps 1e-8
#define succ(x) (1LL<<(x))
#define lowbit(x) (x&(-x))
#define sqr(x) ((x)*(x))
#define mid (x+y>>1)
#define NM 3005
#define nm 100005
#define N 1000005
#define M(x,y) x=max(x,y)
const double pi=acos(-1);
const int inf=1e9+7;
using namespace std;
ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f*x;
}
struct edge{int t;edge*next;}e[2*NM],*h[NM],*o=e;
void add(int x,int y){o->t=y;o->next=h[x];h[x]=o++;}
int n,m,_x,_y,a[NM],root,size[NM],smin,tot;
bitset<nm>ans,d[NM];
bool v[NM];
void dfs1(int x,int f){size[x]=1;link(x)if(!v[j->t]&&j->t!=f)dfs1(j->t,x),size[x]+=size[j->t];}
void getroot(int x,int f){int s=tot-size[x];link(x)if(!v[j->t]&&j->t!=f)getroot(j->t,x),s=max(s,size[j->t]);if(s<smin)root=x,smin=s;}
void dfs(int x,int f){link(x)if(!v[j->t]&&j->t!=f)d[j->t]=(d[x]<<a[j->t]),dfs(j->t,x),d[x]|=d[j->t];}
void div(int x){
dfs1(x,0);
tot=size[x];smin=inf;
getroot(x,0);
v[root]++;
//printf("R:%d\n",root);
d[root].reset();
d[root][a[root]-1]=1;
link(root)if(!v[j->t])d[j->t]=(d[root]<<a[j->t]),dfs(j->t,root),d[root]|=d[j->t];
ans|=d[root];
link(root)if(!v[j->t])div(j->t);
}
int main(){
//freopen("data.in","r",stdin);
int _=read();while(_--){
ans.reset();mem(h);o=e;mem(v);
n=read();m=read();
inc(i,1,n-1){_x=read();_y=read();add(_x,_y);add(_y,_x);}
inc(i,1,n)a[i]=read();
div(1);
inc(i,0,m-1)printf("%d",(int)ans[i]);putchar('\n');
}
return 0;
}