BZOJ4134 ljw和lzr的hack比赛 [Trie/启发式合并/SG函数]

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

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://acxblog.site/archives/sol-bzoj4134.html
文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。