[SHOI2014]三叉神经树

题目描述

计算神经学作为新兴的交叉学科近些年来一直是学术界的热点。一种叫做SHOI 的神经组织因为其和近日发现的化合物 SHTSC 的密切联系引起了人们的极大关注。

SHOI 组织由若干个 SHOI 细胞构成,SHOI 细胞之间形成严密的树形结构。每个 SHOI 细胞都有且只有一个输出端,被称为轴突,除了一个特殊的、被称为根细胞的 SHOI 细胞的输出作为整个组织的输出以外,其余细胞的轴突均连向其上级 SHOI 细胞；并且有且只有三个接收端,被称为树突,从其下级细胞或者其它神经组织那里接收信息。SHOI 细胞的信号机制较为简单,仅有

现在给出了一段 SHOI 组织的信息,以及外部神经组织的输入变化情况。请你模拟 SHOI 组织的输出结果。

题解

身体啊。

先考虑每一次修改能影响到的范围，这个比较简单，只能是这个点到根的路径上的所有点。

再次进一步的考虑，发现能够影响到的范围是一段连续的区间。

考虑为什么题目中给的是一颗每个点有三个儿子的树？如果一个节点时是1，那么它的1的儿子树时2或3，也就是d>>1=1，所以我们判断一个节点是否是被激活的就可以用度数/2来判断。

然后考虑某个叶子从1->0的时候，那么有修改的就是从这个叶子往上连续的一段2，和第一个不是2的点。

反之就是往上连续一段1和第一个不是1的点。

这是一个非常重要的性质，有了这个性质之后就可以二分最靠下的不是1/2的点，用&*%*#数据结构维护一下。

题解给的LCT做法非常喵。

我们不用二分，直接在LCT每个节点维护当前链中深度最深的不是1/2的点。

但是有个问题，这是一颗有根树，我们不能makeroot。

那么如何提取一条链?

假设我们的叶子为x，链顶为y，那么access&&splay(x)之后，当前的splay就是从叶子到根的一条链。

然后再splay(y)此时y的右子树就是我们要的链了。

我的写法如果第一个不是1/2的点是根的话要特判，为啥网上的题解都不同特判啊。。

代码

#include<iostream>
#include<cstdio>
#include<queue>
#define N 500009
#define ls ch[x][0]
#define rs ch[x][1]
using namespace std;
queue<int>q;
int ch[N][2],fa[N],v[N*3],rev[N],n1[N],n2[N],n,f[N*3],du[N];
typedef long long ll;
inline ll rd(){
    ll x=0;char c=getchar();bool f=0;
    while(!isdigit(c)){if(c=='-')f=1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
inline bool ge(int x){return ch[fa[x]][1]==x;}
inline bool isroot(int x){return ch[fa[x]][1]!=x&&ch[fa[x]][0]!=x;}
inline void pushup(int x){
    n1[x]=n1[rs];if(!n1[x])n1[x]=(v[x]!=1)?x:n1[ls];
    n2[x]=n2[rs];if(!n2[x])n2[x]=(v[x]!=2)?x:n2[ls];
}
inline void rotate(int x){
    int y=fa[x],o=ge(x);
    ch[y][o]=ch[x][o^1];fa[ch[y][o]]=y;
    if(!isroot(y))ch[fa[y]][ge(y)]=x;fa[x]=fa[y];
    fa[y]=x;ch[x][o^1]=y;pushup(y);pushup(x);
}
inline void pushdown(int x,int tag){
    if(!x)return;
    v[x]^=3;swap(n1[x],n2[x]);rev[x]+=tag;
}
void _pushdown(int x){
    if(!isroot(x))_pushdown(fa[x]);
    if(rev[x])pushdown(ls,rev[x]),pushdown(rs,rev[x]),rev[x]=0;
}
inline void splay(int x){
    _pushdown(x);
    while(!isroot(x)){
        int y=fa[x];
        if(isroot(y))rotate(x);
        else rotate(ge(x)==ge(y)?y:x),rotate(x);
    }
}
inline void access(int x){
    for(int y=0;x;y=x,x=fa[x])splay(x),ch[x][1]=y,pushup(x);
}
int main(){
    n=rd();int x,y,z;
    for(int i=1;i<=n;++i)f[i]=i;
    for(int i=1;i<=n;++i){
        x=rd();y=rd();z=rd();
        if(x>n)f[x]=i;else fa[x]=i,du[i]++;
        if(y>n)f[y]=i;else fa[y]=i,du[i]++;
        if(z>n)f[z]=i;else fa[z]=i,du[i]++;
    }
    for(int i=n+1;i<=3*n+1;++i)v[i]=rd(),v[f[i]]+=v[i];
    for(int i=1;i<=n;++i)if(!du[i])q.push(i);
    while(!q.empty()){
        int u=q.front();q.pop();
        v[fa[u]]+=v[u]>>1;
        if(!--du[fa[u]])q.push(fa[u]);
    }
    int ans=0,qu;
    ans=v[1]>>1;
    qu=rd();
    while(qu--){
        x=rd();v[x]^=1;int ta=v[x]?1:-1;x=f[x];
    //    cout<<x<<" "<<n1[x]<<" "<<n2[x]<<endl;
        access(x);splay(x);
        if(ta==1&&n1[x]){
            x=n1[x];//cout<<"1"<<" haha "<<x<<endl;
            splay(x);
            pushdown(rs,ta);v[x]+=ta;pushup(x);
            if(x==1)ans=v[1]>>1;
        }
        else if(ta==-1&&n2[x]){
            x=n2[x];//cout<<"2"<<" haha "<<x<<endl;
            splay(x);
            pushdown(rs,ta);v[x]+=ta;pushup(x);
            if(x==1)ans=v[1]>>1;
        }
        else{
           pushdown(x,ta);pushup(x);ans^=1; 
        }
        if(ans)puts("1");else puts("0");
    } 
    return 0;
}