最近好像不断在犯低级错误？？

Problem

分曹射覆蜡灯红，膜拜神犇 lzr；
渚清沙白鸟飞回，长跪巨神 ljw。
lzr 就是被称为 hack 狂魔的 qmqmqm，相比很多人都已经知道了。
ljw 虽然没有 lzr 有名，但是在 cf、bc 等比赛里的 hack 次数也是数一数二的。
SD 的这两位神犇今天决定进行一场 hack 比赛。
经过研究，他们决定 hack SD 的另一位神犇 jzh 做过的题。
我们设 jzh 已经做过了 n 道题。这些题目因为知识点之间的联系而形成了一棵树结构。1 号题目 (A+B problem) 是这棵树的根。
因为 slyz 也不乏 hack 高手，所以 jzh 做的这 n 道题有些已经被 hack 了。
现在 ljw 先手，两人轮流操作。一次操作为：选择一道没有被 hack 过的题 x，然后将 x 到 1 的路径上的所有没有被 hack 过的题全部 hack 掉。
无法操作者输。
我们假设 ljw 和 lzr 的智商都是无比的高 (事实也是如此)，都会采取对自己最有利的操作。
ljw 当然想赢下这场比赛了！于是他想算一下最终他能否赢下比赛。如果他能赢，他还想知道在保证他赢的情况下第一步他选择哪些题。
这么简单的问题 ljw 神犇当然会了。不过他想考考你。

Solution

考虑染色相当于删除一条路径分割出几棵子树，即子问题，那么就可以上 SG 函数了。

一棵树的 SG 是所有后继状态的 mex。考虑从下向上维护子树的 SG，所有的后继状态 SG 用 Trie 维护。

那么就可以从启发式合并两棵子树的后继状态思考，剩下的一些子问题如找 mex，Trie 上异或打标记和输出第一次可行解就不说了。

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10, M=N<<1, m=18, G=5e6;
int h[N], to[M], nexp[M], p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }

struct Node *nil;
struct Node {
    Node *ch[2];
    bool end;
    int s, c, fl, tag;
    void pud() {
        if(tag) {
            if(fl!=-1 && (tag&(1<<fl)))
                swap(ch[0], ch[1]);
            ch[0]->tag^=tag, ch[1]->tag^=tag;
            tag=0;
        }
    }
    void upd() { s=ch[0]->s+ch[1]->s+c; }
    Node (int f=0) { fl=f, s=c=0, ch[0]=ch[1]=nil, tag=0; }
} po[G], *pp=po;
void ini() { nil=pp++, nil->ch[0]=nil->ch[1]=nil; }

void ins(Node *&nd, int t, int x) {
    if(nd==nil) nd=pp++, *nd=Node(t);
    if(t==-1) { nd->s=nd->c=1; return; }
    nd->pud();
    ins(nd->ch[bool(x&(1<<t))], t-1, x);
    nd->upd();
}

int sg[N], ssg[N];
void dfs(Node *x, Node *y, int val, int t) {
    if(x->c) { ins(y, m, val); return; }
    if(x==nil) return;
    x->pud();
    dfs(x->ch[0], y, val, t-1);
    dfs(x->ch[1], y, val|(1<<t), t-1);
}
Node* Merge(Node *x, Node *y) {
    if(x==nil) return y;
    if(y==nil) return x;
    if(x->s<y->s) {
        dfs(x, y, 0, m);
        return y;
    }
    else {
        dfs(y, x, 0, m);
        return x;
    }
}
int mex(Node *x, int t, int val) {
    if(x->end || x==nil) return val;
    x->pud();
    if(x->ch[0]->s==(1<<t)) return mex(x->ch[1], t-1, val|(1<<t));
    else return mex(x->ch[0], t-1, val);
}
int hack[N];
Node* dfs2(int x, int fr) {
    Node *nd=nil, *ret;
    int lsg=0;
    for(int u=h[x];u;u=nexp[u]) if(to[u]!=fr) {
        ret=dfs2(to[u], x), ret->tag^=lsg, nd->tag^=sg[to[u]];
        nd=Merge(ret, nd);
        lsg^=sg[to[u]];
    }
    if(!hack[x]) ins(nd, m, lsg);
    sg[x]=mex(nd, m, 0), ssg[x]=lsg;
    return nd;
}
vector<int> ans;
void dfs3(int x, int fr, int osg) {
    if(!hack[x] && !(ssg[x]^osg)) ans.push_back(x);
    for(int u=h[x];u;u=nexp[u]) if(to[u]!=fr) {
        dfs3(to[u], x, osg^ssg[x]^sg[to[u]]);
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0), ini();
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>hack[i];
    int u, v;
    for(int i=0;i<n-1;i++) cin>>u>>v, ins(u, v), ins(v, u);
    dfs2(1, 0);
    if(!sg[1]) cout<<-1<<endl, exit(0);
    dfs3(1, 0, 0);
    sort(ans.begin(), ans.end());
    for(int i=0, j=ans.size(); i<j; i++) cout<<ans[i]<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-bzoj4134.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆