SPOJ COT3 - Combat on a tree

挺好的一个题，算是博弈和 DS 的有机结合

这类问题一眼考虑 SG 函数，同时树上的 SG 函数一般都是从子树向上递推

考虑若某个点的子树内全是黑点，则其 SG 函数为零；否则考虑枚举所有的后继状态

不难发现选中一个白点会把这个子树断成一个森林，这个后继状态的 SG 函数就是每个连通块 SG 函数的异或值

因此可以想要用某种数据结构维护在每个子树内删去一个白点得到的后继状态的 SG 函数值

需要支持的操作有：合并（用来将子树信息向上传递）；修改（合并多个子树时需要整体异或某个值）；查询 mex

用 0/1Trie 即可实现上述所有功能，其中修改可以用类似线段树懒标记的方法，查询 mex 时只需要维护每个子树是否是满二叉树，类似线段树上二分地递归查询即可

总复杂度 \(O(n\log n)\)

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int n,c[N],sg[N],rt[N],x,y; vector <int> v[N],ans;
class Trie
{
    private:
        int ch[N*20][2],full[N*20],tag[N*20],idx;
        inline void pushup(CI now)
        {
            full[now]=full[ch[now][0]]&full[ch[now][1]];
        }
        inline void pushdown(CI now,CI k)
        {
            if (tag[now]) update(ch[now][0],tag[now],k-1),update(ch[now][1],tag[now],k-1),tag[now]=0;
        }
    public:
        inline void insert(int& now,CI x,CI k=19)
        {
            if (!now) now=++idx;
            if (k==-1) return (void)(full[now]=1);
            pushdown(now,k);
            insert(ch[now][(x>>k)&1],x,k-1);
            pushup(now);
        }
        inline void update(CI now,CI mv,CI k=19)
        {
            if (!now||k==-1) return;
            if ((mv>>k)&1) swap(ch[now][0],ch[now][1]);
            tag[now]^=mv;
        }
        inline int merge(CI x,CI y,CI k=19)
        {
            if (!x||!y) return x|y;
            if (k==-1) return full[x]|=full[y],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);
            pushup(x); return x;
        }
        inline int getmex(CI now,CI k=19)
        {
            if (!now||k==-1) return 0;
            pushdown(now,k);
            if (full[ch[now][0]]) return (1<<k)|getmex(ch[now][1],k-1);
            return getmex(ch[now][0],k-1);
        }
}T;
inline void DFS1(CI now=1,CI fa=0)
{
    int ret=0; for (auto to:v[now])
    if (to!=fa) DFS1(to,now),ret^=sg[to];
    for (auto to:v[now]) if (to!=fa)
    T.update(rt[to],ret^sg[to]),rt[now]=T.merge(rt[now],rt[to]);
    if (!c[now]) T.insert(rt[now],ret);
    sg[now]=T.getmex(rt[now]);
    //printf("sg[%d] = %d\n",now,sg[now]);
}
inline void DFS2(CI now=1,CI fa=0,CI pre=0)
{
    int ret=0; for (auto to:v[now]) if (to!=fa) ret^=sg[to];
    if ((ret^pre)==0&&!c[now]) ans.push_back(now);
    for (auto to:v[now]) if (to!=fa) DFS2(to,now,pre^(ret^sg[to]));
}
int main()
{
    scanf("%d",&n); for (RI i=1;i<=n;++i) scanf("%d",&c[i]);
    for (RI i=1;i<n;++i) scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
    if (DFS1(),sg[1]==0) return puts("-1"),0;
    DFS2(); sort(ans.begin(),ans.end());
    for (auto x:ans) printf("%d\n",x);
    return 0;
}