题意

给定 为根的 个结点有根树，定义一个长度为 的序列 合法当且仅当其所有前缀均为包含根的连通块，定义其终点为 的终点到 的路径上第二个结点。

求每个点是否可能为合法的序列的终点。

思路

首先只考虑根的情况，我们发现我们可以取两个不同的子树，然后各加一个点，此时终点不变，但是两个子树的大小减一。

于是我们只需考虑重儿子，因为只有重儿子的大小会超过子树大小的一半。

设 为只考虑 的子树（根也假设为 ），可能的终点距离 的最小值。

那么就有两种情况（设 为重儿子）：

第一种表示重儿子做完之后，重儿子以外的结点能够把终点拉回 ，那么这个时候终点能不能在 就取决于子树的奇偶性，因为我们只能一对一对地消去结点。

第二种表示不能拉回 ，那么这时其他所有结点显然都应该被用于将终点拉回 。

（ 表示 是没用的。）

---

然后考虑将这个 DP 拓展到每一个结点上，注意到根到 的路径上这些结点都是没用的，因为它们必须顺次使用，而且在这些结点使用完之前，没有任何结点能将终点拉向 ，于是它们的唯一作用就是将终点拉向 。

于是我们可以先将它们使用掉，这样终点当前就位于 ，然后考虑其他所有的子树，它们的根显然不变，于是所有我们预处理的信息和上面的 DP 式都仍然生效，这样只需维护出新的重儿子即可，只有两种可能，一是 本身的重儿子，二是 路径上的结点的重儿子（或次重儿子，如果下一个结点在重儿子上的话）。

这些都容易维护。

CODE

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=100010,FSIZE=1<<26;
int w,tn,n,sz[N],f[N],s[N][2],ans[N];
vector<int> t[N];
char BuF[FSIZE],*InF=BuF;
template<typename T>void read(T &x){
    for(;48>*InF||*InF>57;++InF);
    for(x=0;47<*InF&&*InF<58;x=x*10+(*InF++^48));
}
void pre(int x,int fa){
    sz[x]=1;
    s[x][0]=s[x][1]=0;
    for(int i:t[x])
        if(i!=fa){
            pre(i,x);
            sz[x]+=sz[i];
            if(sz[i]>sz[s[x][0]]){
                s[x][1]=s[x][0];
                s[x][0]=i;
            }else if(sz[i]>sz[s[x][1]]) s[x][1]=i;
        }
}
void dfs(int x,int fa){
    for(int i:t[x])
        if(i!=fa) dfs(i,x);
    if(f[s[x][0]]+1<=sz[x]-sz[s[x][0]]-1) f[x]=~sz[x]&1;
    else f[x]=f[s[x][0]]+1-(sz[x]-sz[s[x][0]]-1);
}
void get(int x,int fa,int up,int dp){
    int mx=sz[s[x][0]]>sz[up]?s[x][0]:up;
    if(f[mx]+1<=n-dp-sz[mx]) ans[x]=~(n-dp)&1;
    else ans[x]=0;
    for(int i:t[x])
        if(i!=fa) get(i,x,mx==i?sz[s[x][1]]>sz[up]?s[x][1]:up:mx,dp+1);
}
void work(){
    read(n);
    for(int i=1;i<=n;++i) t[i].clear();
    for(int i=1,x,y;i<n;++i){
        read(x);read(y);
        t[x].push_back(y);
        t[y].push_back(x);
    }
    pre(1,0);
    dfs(1,0);
    if(w==3){
        printf("%d\n",!f[1]);
        return;
    }
    get(1,0,0,1);
    for(int i=1;i<=n;++i) printf("%d",ans[i]);
    puts("");
}
int main(){
    fread(BuF,1,FSIZE,stdin);
    read(w);
    f[0]=sz[0]=0xf0000000;
    for(read(tn);tn--;work());
    return(0);
}