[SHOI2014]三叉神经树

旧城等待， 2022-01-12 10:43 152阅读 0赞

[\[SHOI2014\]三叉神经树][SHOI2014]

不是那么裸的LCT题

基本凭借一己之力AC了此题（多亏了标签+std对拍）

分析性质

自底向上进行0/1的修改

一定是修改的自底向上的一段链！

并且这些点的儿子之前都是恰好本身的颜色儿子多一个

可以整链找到最上面的不能更新的点，然后整链打标记

但是，扣去某个儿子剩下的儿子的sz0和sz1不好直接处理

LCT可以从1，access(x)劈出一条实链，不妨这个链上的儿子不进行统计，只统计虚儿子！

sz0==sz1都是临界的。就可以了

具体：

LCT维护：fa，child\[0/1\]

id\[0/1\]表示找0/1来讲最深的**不好**的点（不满足sz0=sz1的0/1点或者本身颜色是1/0的）（最浅好点还不能跨过不好点，麻烦）

tag，翻转颜色标记

mx，所在实链最深点，便于直接更新id\[0/1\]（数据水，没必要233333）

wrk函数，access，splay，找到id\[\]=y，如果有，splay(y)，tag右儿子

否则，splay(1)，tag(1)，colort^=1;

#include<bits/stdc++.h>
    #define reg register int
    #define il inline
    #define fi first
    #define se second
    #define mk(a,b) make_pair(a,b)
    #define numb (ch^'0')
    using namespace std;
    typedef long long ll;
    template<class T>il void rd(T &x){
        char ch;x=0;bool fl=false;
        while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
        for(x=numb;isdigit(ch=getchar());x=x*10+numb);
        (fl==true)&&(x=-x);
    }
    template<class T>il void output(T x){
        if(x/10)output(x/10);putchar(x%10+'0');}
    template<class T>il void ot(T x){
        if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
    template<class T>il void prt(T a[],int st,int nd){
        for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}
    
    namespace Miracle{
    const int N=1500000+5;
    int n,q;
    struct node{
        int ch[2],fa;
        int co;
        int lsz[2];
        int mx;//zui shen dian
        int id[2];//deepest nogood point
        int tag;
        bool nogood(int c){
            return (co!=c)||(co==c&&lsz[c]>=2);
        }
        void op(){
            cout<<" ch[0] "<<ch[0]<<" ch[1] "<<ch[1]<<endl;
            cout<<" lsz[0] "<<lsz[0]<<" lsz[1] "<<lsz[1]<<endl;
            cout<<" id[0] "<<id[0]<<" id[1] "<<id[1]<<endl;
            cout<<" co "<<co<<endl;
        }
    }t[N];
    bool nrt(int x){
        return t[t[x].fa].ch[0]==x||t[t[x].fa].ch[1]==x;
    }
    void pushup(int x){
        if(t[x].ch[1]&&t[t[x].ch[1]].id[0]){
            t[x].id[0]=t[t[x].ch[1]].id[0];
        }else if(t[x].nogood(0)){
            t[x].id[0]=x;
        }else if(t[x].ch[0]&&t[t[x].ch[0]].id[0]){
            t[x].id[0]=t[t[x].ch[0]].id[0];
        }else t[x].id[0]=0;
        
        if(t[x].ch[1]&&t[t[x].ch[1]].id[1]){
            t[x].id[1]=t[t[x].ch[1]].id[1];
        }else if(t[x].nogood(1)){
            t[x].id[1]=x;
        }else if(t[x].ch[0]&&t[t[x].ch[0]].id[1]){
            t[x].id[1]=t[t[x].ch[0]].id[1];
        }else t[x].id[1]=0;
        
        if(t[x].ch[1]) t[x].mx=t[t[x].ch[0]].mx;
        else t[x].mx=x;
    }
    void tag(int x){
        t[x].tag^=1;
        //if(x<=n) 
        t[x].co^=1;
        t[x].id[t[x].co]=0;
        t[x].id[t[x].co^1]=t[x].mx;
    }
    void pushdown(int x){
        if(t[x].tag){
            tag(t[x].ch[0]);
            tag(t[x].ch[1]);
            t[x].tag=0;
        }
    }
    void rotate(int x){
        int y=t[x].fa,d=t[y].ch[1]==x;
        t[t[y].ch[d]=t[x].ch[!d]].fa=y;
        if(nrt(y)) t[t[x].fa=t[y].fa].ch[t[t[y].fa].ch[1]==y]=x;
        else t[x].fa=t[y].fa;
        t[t[x].ch[!d]=y].fa=x;
        pushup(y);
    }
    int sta[N];
    void splay(int x){
        int z=0,y=x;
        sta[++z]=y;
        while(nrt(y)) y=t[y].fa,sta[++z]=y;
        while(z) pushdown(sta[z--]);
        while(nrt(x)){
            y=t[x].fa,z=t[y].fa;
            if(nrt(y)){
                rotate((t[y].ch[0]==x)==(t[z].ch[0]==y)?y:x);
            }
            rotate(x);
        }
        pushup(x);
    }
    int bac(int x){
        if(!t[x].ch[1]) return 0;
        pushdown(x);
        x=t[x].ch[1];while(t[x].ch[0]) pushdown(x),x=t[x].ch[0];return x;
    }
    int pre(int x){
        pushdown(x);
        while(t[x].ch[0]) pushdown(x),x=t[x].ch[0];return x;
    }
    void access(int x){
    //    cout<<" access "<<x<<endl;
        for(reg y=0;x;y=x,x=t[x].fa){
    //        cout<<" x "<<x<<"  y "<<y<<endl;
            splay(x);
            int pr=pre(y),bc=bac(x);
            if(pr) t[x].lsz[t[pr].co]--;
            if(bc) t[x].lsz[t[bc].co]++;
    //        cout<<" pre "<<pr<<" bac "<<bc<<endl;
            t[x].ch[1]=y;
            pushup(x);
    //        t[x].op();
        }
    }
    int cort;
    void wrk(int x,int c){
        access(x);
        splay(x);
    //    cout<<"splyaxx "<<endl;
    //    t[x].op();
        if(t[x].id[c^1]){
            int y=t[x].id[c^1];
    //        cout<<" -------------change "<<y<<endl;
            splay(y);
            tag(t[y].ch[1]);
        }else{
    //        cout<<"************-changert"<<endl;
            cort=c;
            splay(1);
            tag(1);
    //        t[1].op();
        }
    }
    int    col[N];
    struct edge{
        int nxt,to;}e[2*N];int hd[N],cnt;
    void add(int x,int y){e[++cnt].nxt=hd[x];e[cnt].to=y;hd[x]=cnt;}
    void dfs(int x){
        for(reg i=hd[x];i;i=e[i].nxt){dfs(e[i].to);t[x].lsz[t[e[i].to].co]++;t[e[i].to].fa=x;}
        if(t[x].lsz[1]>t[x].lsz[0]) t[x].co=1;
    }
    
    int main(){
        rd(n);
        int x;
        for(reg i=1;i<=n;++i){
            rd(x);add(i,x);rd(x);add(i,x);rd(x);add(i,x);
        }
        for(reg i=n+1;i<=3*n+1;++i) rd(col[i]),t[i].co=col[i];
        dfs(1);
        for(reg i=1;i<=n;++i) pushup(i);//to make id
    //    for(reg i=1;i<=n;++i){
    //        cout<<i<<" : ";
    //        t[i].op();
    //        cout<<endl;
    //    }
        rd(q);
        cort=t[1].co;
    //    cout<<" pre cort "<<cort<<endl;
        while(q--){
            rd(x);wrk(x,col[x]^1);col[x]^=1;
            printf("%d\n",cort);
        }
        return 0;
    }
    
    }
    signed main(){
        Miracle::main();
        return 0;
    }
    
    /*
       Author: *Miracle*
       Date: 2019/3/14 17:06:41
    */

pushdown注意更新全部的信息！，id\[0/1\]必须考虑到

直接ch相连不一定是实际相连的。

额外记录的col主函数中是要变的。因为可能不能实时pushdown

写法有些毒瘤。。。。

FlashHu提供一种简单多的方法：

就是记录点权0/1/2/3，即颜色为1的儿子个数

找自底向上极长的连续1/2点权的链，都变成1/0颜色

如果：

![1399631-20190314204433510-1103509961.png][]

不可能更新到那个1的儿子，因为那个1的点权至少是2，所以没有问题！

然后，就成静态的了。。。。

LCT、树剖就随便做了。。。。。。

转载于:https://www.cnblogs.com/Miracevin/p/10533257.html

[SHOI2014]: https://www.luogu.org/problemnew/show/P4332
[1399631-20190314204433510-1103509961.png]: /images/20220109/a6264b5179f1408dbde35ef35ad8ee49.png