题解 SP11414 【COT3 - Combat on a tree】

发现本题为公平组合游戏,因此考虑用 \(\text{SG}\) 函数来解决。

设 \(\text{SG}(x)\) 为以 \(x\) 为根的子树的 \(\text{SG}\) 值。对于点 \(x\),可以枚举其子树内的每一个白点,删去该点到 \(x\) 的所有点,然后以 \(x\) 为根的子树会分裂为一个森林,也就是 \(x\) 状态可以转移到这个森林的状态,一个森林的 \(\text{SG}\) 值为每棵树的 \(\text{SG}\) 值异或和。\(\text{SG}(x)\) 即为子树内所有白点删去后形成的森林对应的 \(\text{SG}\) 值取 \(\text{mex}\)。

考虑用数据结构来优化这个过程,每个节点上都用一个 \(01\ Trie\) 来维护其子树内所有白点删去后对应的森林的 \(\text{SG}\) 值。设 \(y\) 为 \(x\) 的一个儿子,那么 \(y\) 对应的 \(01\ Trie\) 中维护的信息还需再异或上 \(x\) 其他儿子的 \(\text{SG}\) 值的异或和才是其正确的信息。整体异或一个值可以用打标记,交换左右儿子来实现。加上 \(y\) 的贡献即为将 \(y\) 对应的 \(01\ Trie\) 合并到 \(x\) 上。

最后再 \(dfs\) 一遍,若一个点的后继状态为必败状态,则该点可以作为第一步选的点。

#include<bits/stdc++.h>
#define maxn 200010
#define maxm 4000010
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 n,tot,cnt;
int c[maxn],sg[maxn],ans[maxn],rt[maxn],ch[maxm][2],tag[maxm];
bool cov[maxm];
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 pushtag(int p,int k,int x)
{
    if(k==-1) return;
    if(x>>k&1) swap(ch[p][0],ch[p][1]);
    tag[p]^=x;
}
void pushdown(int p,int k)
{
    if(!tag[p]) return;
    pushtag(ch[p][0],k-1,tag[p]),pushtag(ch[p][1],k-1,tag[p]),tag[p]=0;
}
void insert(int &p,int k,int x)
{
    if(!p) p=++tot;
    if(k==-1)
    {
        cov[p]=true;
        return;
    }
    insert(ch[p][x>>k&1],k-1,x);
    cov[p]=cov[ch[p][0]]&cov[ch[p][1]];
}
int merge(int x,int y,int k)
{
    if(!x||!y) return x+y;
    if(k==-1)
    {
        cov[x]|=cov[y];
        return x;
    }
    pushdown(x,k),pushdown(y,k);
    ch[x][0]=merge(ch[x][0],ch[y][0],k-1);
    ch[x][1]=merge(ch[x][1],ch[y][1],k-1);
    cov[x]=cov[ch[x][0]]&cov[ch[x][1]];
    return x;
}
int mex(int p,int k)
{
    if(!p||k==-1) return 0;
    pushdown(p,k);
    if(cov[ch[p][0]]) return (1<<k)|mex(ch[p][1],k-1);
    return mex(ch[p][0],k-1);
}
void dfs_get(int x,int fa)
{
    int v=0;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(y==fa) continue;
        dfs_get(y,x),v^=sg[y];
    }
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(y==fa) continue;
        pushtag(rt[y],20,v^sg[y]);
        rt[x]=merge(rt[x],rt[y],20);
    }
    if(!c[x]) insert(rt[x],20,v);
    sg[x]=mex(rt[x],20);
}
void dfs_ans(int x,int fa,int v)
{
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(y==fa) continue;
        v^=sg[y];
    }
    if(!v&&!c[x]) ans[++cnt]=x;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(y==fa) continue;
        dfs_ans(y,x,v^sg[y]);
    }
}
int main()
{
    read(n);
    for(int i=1;i<=n;++i) read(c[i]);
    for(int i=1;i<n;++i)
    {
        int x,y;
        read(x),read(y);
        add(x,y),add(y,x);
    }
    dfs_get(1,0);
    if(!sg[1]) puts("-1");
    else
    {
        dfs_ans(1,0,0),sort(ans+1,ans+cnt+1);
        for(int i=1;i<=cnt;++i) printf("%d ",ans[i]);
    }
    return 0;
}
上一篇:篇?-uvm_test


下一篇:育种值 表型值 回归系数 相关系数 遗传力之间的关系