题目
题目链接：https://www.luogu.com.cn/problem/P4332
计算神经学作为新兴的交叉学科近些年来一直是学术界的热点。一种叫做SHOI 的神经组织因为其和近日发现的化合物 SHTSC 的密切联系引起了人们的极大关注。
SHOI 组织由若干个 SHOI 细胞构成,SHOI 细胞之间形成严密的树形结构。每个 SHOI 细胞都有且只有一个输出端,被称为轴突,除了一个特殊的、被称为根细胞的 SHOI 细胞的输出作为整个组织的输出以外,其余细胞的轴突均连向其上级 SHOI 细胞；并且有且只有三个接收端,被称为树突,从其下级细胞或者其它神经组织那里接收信息。SHOI 细胞的信号机制较为简单,仅有 (0) 和 (1) 两种。每个 SHOI 细胞根据三个输入端中 (0) 和 (1) 信号的多寡输出较多的那一种。
现在给出了一段 SHOI 组织的信息,以及外部神经组织的输入变化情况。请你模拟 SHOI 组织的输出结果。
(n,qleq 5 imes 10^5)。
思路
我们记 (a_i) 表示节点 (x) 的三个儿子中，(1) 的出现次数。下文点权也指代 (a)。
对于一次修改，不妨设这次修改是把一个叶子从 (0) 改为 (1)。我们找到这个叶子的父亲 (x)，不难发现，需要修改的部分就是从 (x) 一直往上，且点权均为 (1) 的一段，再加上这一段上面的第一个节点。我们需要把这一段全部 (+1)。
把叶子从 (1) 修改为 (0) 同理，只需要找到一段全为 (2) 的。
考虑用 LCT 维护这个过程。对于每一棵 Splay，维护其中深度最深的，且点权不为 (1/2) 的点的编号。对于一次修改操作，假设为从 (0) 改为 (1)，我们就直接把 (x) access 后 splay 到根，查询当前这棵 Splay 的深度最大的不为 (1) 的点，把这个点旋到根后，只需要把这个点和他的右子树全部加一即可。
因为如果我们需要把一个区间加一，那么这个区间肯定是全为 (1) 的，所以可以直接把最深的点权不为 (1/2) 的点的编号交换一下。
需要注意的是，如果整条链的点权都是 (1)，那么只需要在根节点上直接修改即可。
时间复杂度 (O(Qlog n))。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=500010;
int n,Q,fat[N*3],a[N*3],son[N][3];
int read()
{
int d=0; char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) d=(d<<3)+(d<<1)+ch-48,ch=getchar();
return d;
}
struct LCT
{
int val[N],fa[N],id[N][2],ch[N][2];
bool lazy[N];
bool pos(int x) { return x==ch[fa[x]][1]; }
bool notrt(int x) { return x==ch[fa[x]][0] || x==ch[fa[x]][1]; }
void pushup(int x)
{
int lc=ch[x][0],rc=ch[x][1];
id[x][0]=id[rc][0] ? id[rc][0] : (val[x]==1 ? id[lc][0] : x);
id[x][1]=id[rc][1] ? id[rc][1] : (val[x]==2 ? id[lc][1] : x);
}
void update(int x)
{
val[x]^=3; lazy[x]^=1;
swap(id[x][0],id[x][1]);
}
void pushdown(int x)
{
if (lazy[x])
{
if (ch[x][0]) update(ch[x][0]);
if (ch[x][1]) update(ch[x][1]);
lazy[x]=0;
}
}
void rotate(int x)
{
int y=fa[x],z=fa[y],k=pos(x),c=ch[x][k^1];
if (notrt(y)) ch[z][pos(y)]=x; ch[x][k^1]=y; ch[y][k]=c;
if (c) fa[c]=y; fa[y]=x; fa[x]=z;
pushup(y); pushup(x);
}
void splay(int x)
{
stack<int> st; st.push(x);
for (int i=x;notrt(i);i=fa[i]) st.push(fa[i]);
for (;st.size();st.pop()) pushdown(st.top());
for (;notrt(x);rotate(x))
{
int y=fa[x];
if (notrt(y)) rotate(pos(x)==pos(y) ? y : x);
}
}
void access(int x)
{
for (int y=0;x;y=x,x=fa[x])
{
splay(x); ch[x][1]=y;
pushup(x);
}
}
}lct;
int dfs(int x)
{
if (x>n) return a[x];
a[x]=dfs(son[x][0])+dfs(son[x][1])+dfs(son[x][2]);
lct.fa[x]=fat[x]; lct.val[x]=a[x];
lct.pushup(x); a[x]=(a[x]>=2);
return a[x];
}
int main()
{
n=read();
for (int i=1;i<=n;i++)
for (int j=0;j<=2;j++)
son[i][j]=read(),fat[son[i][j]]=i;
for (int i=n+1;i<=3*n+1;i++) a[i]=read();
dfs(1);
Q=read();
while (Q--)
{
int x=read(); a[x]^=1;
int v=a[x]; x=fat[x];
lct.access(x); lct.splay(x);
if (v)
{
if (!lct.id[x][0]) lct.update(x);
else
{
x=lct.id[x][0];
lct.splay(x); lct.val[x]++;
if (lct.ch[x][1]) lct.update(lct.ch[x][1]);
lct.pushup(x);
}
}
else
{
if (!lct.id[x][1]) lct.update(x);
else
{
x=lct.id[x][1];
lct.splay(x); lct.val[x]--;
if (lct.ch[x][1]) lct.update(lct.ch[x][1]);
lct.pushup(x);
}
}
lct.splay(1);
cout<<(lct.val[1]>=2)<<"
";
}
return 0;
}