[SHOI2014] 三叉神经树

Description

给定一棵以 $1$ 为根的有 $3n+1$ 个节点的树，树上每个节点均有一个输出端。树上有 $n$ 个节点有 $3$ 个子节点，其余的 $2n+1$ 个节点无子节点（也就是叶子）。$2n+1$ 个节点的初始值均为 $0/1$ ，并且已经提前知道；剩余 $n$ 个节点的值为其 $3$ 个子节点中出现次数最多的值。$q$ 次询问，每次改变一个叶子节点的值，求操作后根节点的值。
$n,q\leq 5\times 10^5$

Solution

可以发现每次修改必定是修改一条自底向上的链。并且这条链有一些比较明显的性质：

• 链上的点必定修改成同一值
• $u$ 改变时 fa[u] 也改变，当且仅当 fa[u] 的另外两个子节点的值恰好一个 $1$ 一个 $0$

但是如何快速查询修改链的顶端节点以及修改链上的点值呢？
不妨再深入找找性质。
当叶子节点 $u$ 从 0 变为 1 时，若其父节点 $v$ 目前的子节点权值和为 1 ，那么父节点将会由 0 变为 1 ，继续上传；否则就此打住。同理， $v$ 能够再影响到 $v$ 的父节点 $k$ 当且仅当 $k$ 的目前的子节点权值和为 1 。当叶子节点从 1 变为 0 的情况也是类似的，只不过是要求目前的子节点权值和为 2 。
问题至此就水落石出了。我们将那 $n$ 个节点按照子节点的权值和分为 4 类，分别为 0-3 。
链上的查询只会在碰到深度最深的非 1/2 类节点时停下来，于是我们在 LCT 上维护下这个东西就行了。
发现链上修改就是区间 $+1/-1$ ，直接打标记也可以做。

复杂度 $\mathcal{O}(q\log_2{n})$ 。
这道题当然也可以不用 LCT 而是用树链剖分。事实上，这只是用线段树维护链还是用 Splay 维护链的问题。而由于树链剖分时首先需要把链剖成 log 段，故在本题中，树链剖分的复杂度不如 LCT 。

Code

const int N=2e6+5;
using namespace std;
int n,q;
vector<int>child[N];
namespace LCT{
#define lc(x) c[x][0]
#define rc(x) c[x][1]
    int v[N],fa[N],one[N],two[N],tag[N],c[N][2];
    bool isrt(int x){
        return fa[x]==0 || (lc(fa[x])!=x&&rc(fa[x])!=x);
    }
    void update(int x){
        if(one[rc(x)]) one[x]=one[rc(x)];
        else if(v[x]^1) one[x]=x;
        else one[x]=one[lc(x)];
        if(two[rc(x)]) two[x]=two[rc(x)];
        else if(v[x]^2) two[x]=x;
        else two[x]=two[lc(x)];
    }
    void pushmk(int x,int d){
        tag[x]+=d;swap(one[x],two[x]);v[x]^=3;
    }
    void pushdn(int x){
        pushmk(lc(x),tag[x]);
        pushmk(rc(x),tag[x]);
        tag[x]=0;
    }
    void rotate(int x){
        int y=fa[x],z=fa[y],t=rc(y)==x;
        if(!isrt(y)) c[z][rc(z)==y]=x;fa[x]=z;
        c[y][t]=c[x][t^1];fa[c[x][t^1]]=y;
        c[x][t^1]=y;fa[y]=x;
        update(y),update(x);
    }
    void pushall(int x){
        if(!isrt(x)) pushall(fa[x]);
        if(tag[x]) pushdn(x);
    }
    void splay(int x){
        pushall(x);
        while(!isrt(x)){
            int y=fa[x],z=fa[y];
            if(!isrt(y))
                ((rc(y)==x)^(rc(z)==y))?rotate(x):rotate(y);
            rotate(x);
        }
        update(x);
    }
    void access(int x){
        int times=0;
        for(int i=0;x;x=fa[i=x])
            splay(x),rc(x)=i,update(x),++times;
    }
}
using namespace LCT;
void DFS(int p){
    for(auto u:child[p])
        DFS(u),v[p]+=(v[u]>>1);
    if(p<=n) update(p);
}
int main(){
    
    r(n);
    for(int i=1;i<=n;++i)
    for(int j=1,x;j<=3;++j)
        r(x),child[i].push_back(x),fa[x]=i;
    for(int i=n+1;i<=3*n+1;++i)
        r(v[i]),v[i]<<=1;
    DFS(1);
    r(q);int ans=v[1]>>1;
    for(int i=1,x;i<=q;++i){
        r(x);
        int tp=(v[x]^=2)-1;
        access(x=fa[x]);splay(x);
        if((~tp?one:two)[x]){ // -1:1to0 1:0to1
            x=(~tp?one:two)[x];
            splay(x);pushmk(rc(x),tp);update(rc(x));
            v[x]+=tp;update(x);
        }
        else pushmk(x,tp),update(x),ans^=1;
        w(ans);
    }
    return 0;
}