正题
题目链接:https://www.luogu.com.cn/problem/P4332
题目大意
给出(n)个点的一棵有根三叉树，保证每个点的儿子个数为(3)或者(0)，每个叶子有一个权值(0)或(1)，每个非叶子节点的权值是它儿子中权值较多的那个，每次修改一个叶子的权值，求根节点的权值。
(1leq n,qleq 5 imes 10^5)
解题思路
修改一个节点会影响的权值显然是它到根节点路径上的一个前缀。
然后考虑什么样的节点会受到影响，如果(0)改为(1)那么一路上原来恰好为两个(0)的节点就会被修改，那么我们的思路是考虑找到这条路径上第一个(1)的个数不为(1)的节点。
而且考虑上修改的话十分的麻烦，因为(O(nlog^2 n))过不去所以不考虑树剖，可以考虑一下(LCT)。
我们可以先联通修改点到根的节点，然后在(Splay)上二分出第一个不为(1)的节点，然后对于它和它的右子树暴力修改即可。
(1)改为(0)同理，维护第一个不为(2)的节点即可。
时间复杂度(O(nlog n))
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
const int N=2e6+10;
int n,m,ans,fa[N],v[N],w1[N],w2[N],lazy[N],t[N][2];
vector<int> G[N];stack<int> s;
bool Nroot(int x)
{return fa[x]&&(t[fa[x]][0]==x||t[fa[x]][1]==x);}
bool Direct(int x)
{return t[fa[x]][1]==x;}
void PushUp(int x){
if(w1[t[x][1]])w1[x]=w1[t[x][1]];
else if(v[x]!=1)w1[x]=x;
else w1[x]=w1[t[x][0]];
if(w2[t[x][1]])w2[x]=w2[t[x][1]];
else if(v[x]!=2)w2[x]=x;
else w2[x]=w2[t[x][0]];
return;
}
void PushR(int x,int w)
{v[x]^=3;swap(w1[x],w2[x]);lazy[x]+=w;return;}
void PushDown(int x){
if(!lazy[x])return;
PushR(t[x][0],lazy[x]);
PushR(t[x][1],lazy[x]);
lazy[x]=0;return;
}
void Rotate(int x){
int y=fa[x],z=fa[y];
int xs=Direct(x),ys=Direct(y);
int w=t[x][xs^1];
if(Nroot(y))t[z][ys]=x;
t[x][xs^1]=y;t[y][xs]=w;
if(w)fa[w]=y;fa[y]=x;fa[x]=z;
PushUp(y);PushUp(x);return;
}
void Splay(int x){
int y=x;s.push(x);
while(Nroot(y))y=fa[y],s.push(y);
while(!s.empty())PushDown(s.top()),s.pop();
while(Nroot(x)){
y=fa[x];
if(!Nroot(y))Rotate(x);
else if(Direct(x)==Direct(y))
Rotate(y),Rotate(x);
else Rotate(x),Rotate(x);
}
return;
}
void Access(int x){
for(int y=0;x;y=x,x=fa[x])
Splay(x),t[x][1]=y,PushUp(x);
return;
}
void Updata(int x){
int op=(v[x]^=2);
x=fa[x];Access(x);Splay(x);
if(op){
if(w1[x]){
x=w1[x];Splay(x);
PushR(t[x][1],1);PushUp(t[x][1]);
v[x]++;PushUp(x);
}
else ans=!ans,PushR(x,1),PushUp(x);
}
else{
if(w2[x]){
x=w2[x];Splay(x);
PushR(t[x][1],-1);PushUp(t[x][1]);
v[x]--;PushUp(x);
}
else ans=!ans,PushR(x,-1),PushUp(x);
}
return;
}
void dfs(int x){
for(int i=0;i<G[x].size();i++){
int y=G[x][i];dfs(y);
v[x]+=(v[y]>>1);
}
PushUp(x);
return;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
fa[x]=fa[y]=fa[z]=i;
G[i].push_back(x);
G[i].push_back(y);
G[i].push_back(z);
}
for(int i=n+1;i<=3*n+1;i++)
scanf("%d",&v[i]),v[i]<<=1;
dfs(1);ans=v[1]>>1;
scanf("%d",&m);
while(m--){
int x;scanf("%d",&x);
Updata(x);
printf("%d
",ans);
}
return 0;
}