传送门
树形dp好题啊。
我们用w[i]" role="presentation" style="position: relative;">w[i]w[i]表示以i为根的子树最少可以把在子树外的榕树之心向子树里拉多少距离。
我们令i最大的子树的根为ms" role="presentation" style="position: relative;">msms。
那么有几种情况：
1. size[ms]" role="presentation" style="position: relative;">size[ms]size[ms]过大，用i其它的子树无法把榕树之心拉回到i去，这个时候有：
w[i]=w[ms]−(size[i]−1−size[ms])" role="presentation" style="position: relative;">w[i]=w[ms]−(size[i]−1−size[ms])w[i]=w[ms]−(size[i]−1−size[ms])。
2. size[ms]" role="presentation" style="position: relative;">size[ms]size[ms]不够大，用i其它子树可以把榕树之心拉回去，但有可能会让榕树之心多走一步。
因此有：
w[i]=(size[i]−1)" role="presentation" style="position: relative;">w[i]=(size[i]−1)w[i]=(size[i]−1) mod" role="presentation" style="position: relative;">modmod 2" role="presentation" style="position: relative;">22
这样我们可以推出w[1]~w[n]。
并且判断整棵树的根节点是否能被凑出。
接下来怎么做呢？
对于一个点i，我们需要判断它是否能被凑出。
我们令depth[i]表示i的深度，其中depth[root]=1" role="presentation" style="position: relative;">depth[root]=1depth[root]=1
首先，如果size[roott]−depth[i]" role="presentation" style="position: relative;">size[roott]−depth[i]size[roott]−depth[i]不是偶数，说明除开root~i这条路径外的其它点一定无法全部抵消，一定会剩下一个，因此最后榕树之心拉不到i节点上。
于是size[root]−depth[i]" role="presentation" style="position: relative;">size[root]−depth[i]size[root]−depth[i]应该为偶数，继续讨论。
这时我们需要把root−>i" role="presentation" style="position: relative;">root−>iroot−>i这条路径看成整个树的根节点，然后把其它的都看成自己的子树像之前求w数组时候那样讨论一下就ok了。
代码：
#include<bits/stdc++.h>
#define mod 998244353
#define N 300005
#define rt 1
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int W,t,n,cnt=0,siz[N],first[N],mx1[N],mx2[N],dep[N],f[N],w[N],ans[N];
struct edge{int v,next;}e[N<<1];
inline void add(int u,int v){e[++cnt].v=v,e[cnt].next=first[u],first[u]=cnt;}
inline void dfs1(int p,int fa){
siz[p]=1,mx1[p]=mx2[p]=0;
for(int i=first[p];i;i=e[i].next){
int v=e[i].v;
if(v==fa)continue;
dep[v]=dep[p]+1,dfs1(v,p),siz[p]+=siz[v];
if(siz[mx1[p]]<siz[v])mx2[p]=mx1[p],mx1[p]=v;
else if(siz[mx2[p]]<siz[v])mx2[p]=v;
}
if(siz[p]-1>=siz[mx1[p]]+w[mx1[p]])w[p]=(siz[p]-1)%2;
else w[p]=w[mx1[p]]-(siz[p]-1-siz[mx1[p]]);
++w[p];
}
inline void dfs2(int p,int fa){
ans[p]=0;
if((siz[rt]-dep[p])%2==0){
int v=f[p];
if(siz[v]<siz[mx1[p]])v=mx1[p];
if(siz[rt]-dep[p]-siz[v]-w[v]>=0)ans[p]=1;
}
for(int i=first[p];i;i=e[i].next){
int v=e[i].v;
if(v==fa)continue;
f[v]=f[p];
if(v!=mx1[p]&&siz[mx1[p]]>siz[f[v]])f[v]=mx1[p];
else if(siz[mx2[p]]>siz[f[v]])f[v]=mx2[p];
dfs2(v,p);
}
}
int u,v;
int main(){
W=read(),t=read();
while(t--){
n=read(),cnt=0,memset(first,0,sizeof(first));
for(int i=1;i<n;++i)u=read(),v=read(),add(u,v),add(v,u);
dep[1]=1,dfs1(1,1),f[1]=0,dfs2(1,1);
if(W==3)putchar(ans[1]^48);
else for(int i=1;i<=n;++i)putchar(ans[i]^48);
puts("");
}
return 0;
}