题解

本题使用树形DP + 换根DP求解。

算法思路：

1. 第一次DFS（dfs1）：以节点1为根，自底向上计算每个子树的信息

   • 记录每个节点的子树大小 sz[u]
   • 找出每个节点的重儿子 son[u]（子树最大的儿子）
   • 计算 f[u]：表示以 $u$ 为根的子树内的某个博弈值

2. 第二次DFS（dfs2）：换根DP，计算每个节点作为根时的答案

   • 对于每个节点 $u$，考虑它作为整棵树的根时的情况
   • 通过维护虚拟的重儿子和子树大小，快速计算答案
   • ans[u] 存储节点 $u$ 作为根时的答案

3. 核心转移方程：

   • 若 $f[son] + 1 \leq size - sz[son] - 1$，则答案为 $(size - 1) \& 1$
   • 否则答案为 $f[son] + 1 - (size - sz[son] - 1)$

这是一道博弈论与树形DP结合的高难度题目，需要理解换根DP的技巧。

#include<bits/stdc++.h>
#define reg register
// #define int long long
inline int read(){
    reg int x=0,k=1; reg char ch=getchar();    
    while (ch<'0'||ch>'9') (ch=='-')&&(k=-1),ch=getchar();
    while ('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*k;
}
const int N=1e6+10;
int n,W,f[N],ans[N],sz[N],son[N];
std::vector<int> G[N];
void dfs1(reg int u,reg int fa=0){
    sz[u]=1,son[u]=f[u]=0;
    for (auto v:G[u]) if (v^fa) dfs1(v,u),sz[u]+=sz[v],sz[son[u]]<sz[v]?son[u]=v:0;
    if (!son[u]) return;
    if (f[son[u]]+1<=sz[u]-sz[son[u]]-1) f[u]=sz[u]-1&1;
    else f[u]=f[son[u]]+1-(sz[u]-sz[son[u]]-1);
}
void dfs2(reg int u,reg int pre=0,reg int siz=0,reg int fa=0){
    if (u>1){
        reg int Son,Sz=siz+sz[u];
        if (sz[son[u]]>sz[pre]) Son=son[u]; else Son=pre; 
        // std::cerr<<"<< "<<f[Son]<<" "<<Sz<<" "<<sz[Son]<<"\n";
        if (f[Son]+1<=Sz-sz[Son]-1) ans[u]=Sz-1&1;
        else ans[u]=f[Son]+1-(Sz-sz[Son]-1);
    }
    reg int son2=0;
    for (auto v:G[u]) if (v!=fa&&v!=son[u]) sz[son2]<sz[v]?son2=v:0;
    for (auto v:G[u]) if (v^fa){
        reg int nw=v==son[u]?son2:son[u];
        dfs2(v,sz[pre]>sz[nw]?pre:nw,siz+sz[u]-sz[v]-1,u);
    }
}
inline void work(){
    n=read(); for (reg int i=1;i<=n;i++) G[i].clear();
    for (reg int i=1,u,v;i<n;i++) u=read(),v=read(),G[u].push_back(v),G[v].push_back(u);
    dfs1(1),ans[1]=f[1],dfs2(1);
    if (W==3) putchar((ans[1]==0)+'0'),puts("");
    else{
        for (reg int i=1;i<=n;i++) putchar((ans[i]==0)+'0'); puts("");
    }
}
signed main(){ 
    W=read();
    for (reg int _=read();_--;) work();
    return 0;
}