先只考虑根节点是否合法。发现两个来自不同子树的点可以消去，那么只需判定所有点能否两两消去，使心停留在根节点即可。
发现其可以转化为一个模型：有若干个集合，每个集合内有若干个点，每次可以消去两个来自不同集合的点。设集合点数总和为 (sum)，最大集合点数为 (max)，得：
(sum-max geqslant max) 时，即 (sum geqslant 2max)，若 (sum) 为偶数则能消完，否则会剩下 (1) 个点，消去了 (left lfloor frac{sum}{2} ight floor) 对。
否则会剩下 (max-(sum-max)) 个来自最大集合的点，消去了 (sum-max) 对。
然后将该模型应用到本题，设 (f_x) 为点 (x) 子树内能最多消去多少对点，点 (y) 为点 (x) 儿子中子树大小最大的儿子，得当 (size_x-1 geqslant 2(size_y-f_y)) 时，(f_x=left lfloor frac{size_x-1}{2} ight floor)，否则 (f_x=size_x-1-(size_y-f_y))。
然后考虑如何判定其他节点合法，可以看作心先从根节点移动到了当前节点，那么将根节点到当前节点的链缩成一个点即可。这里需要知道缩点后的最大子树，因此还需处理出每个节点的次大子树。
通过 (sum geqslant 2max) 是否满足和总点数与当前节点深度的奇偶性是否相同来判定即可。
#include<bits/stdc++.h>
#define maxn 200010
using namespace std;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
int type,T,n;
int f[maxn],siz[maxn],dep[maxn],son1[maxn],son2[maxn],ans[maxn];
struct edge
{
int to,nxt;
}e[maxn];
int head[maxn],edge_cnt;
void add(int from,int to)
{
e[++edge_cnt]={to,head[from]},head[from]=edge_cnt;
}
void dfs1(int x,int fa)
{
siz[x]=1,dep[x]=dep[fa]+1,son1[x]=son2[x]=0;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(y==fa) continue;
dfs1(y,x),siz[x]+=siz[y];
if(siz[y]>siz[son1[x]]) son2[x]=son1[x],son1[x]=y;
else if(siz[y]>siz[son2[x]]) son2[x]=y;
}
if(!son1[x]) return;
if(siz[x]-1>=2*(siz[son1[x]]-f[son1[x]])) f[x]=(siz[x]-1)/2;
else f[x]=siz[x]-1-siz[son1[x]]+f[son1[x]];
}
int c(int x,int y)
{
return siz[x]>siz[y]?x:y;
}
void dfs2(int x,int fa,int p)
{
int t=c(p,son1[x]);
if(n-dep[x]>=2*(siz[t]-f[t])) ans[x]=(n&1)==(dep[x]&1);
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(y==fa) continue;
dfs2(y,x,y==son1[x]?c(p,son2[x]):c(p,son1[x]));
}
}
void clear()
{
edge_cnt=0;
memset(head,0,sizeof(head));
memset(ans,0,sizeof(ans));
}
int main()
{
read(type),read(T);
while(T--)
{
clear(),read(n);
for(int i=1;i<n;++i)
{
int x,y;
read(x),read(y);
add(x,y),add(y,x);
}
dfs1(1,0),dfs2(1,0,0);
if(type==3) printf("%d",ans[1]);
else for(int i=1;i<=n;++i) printf("%d",ans[i]);
putchar('
');
}
return 0;
}