不是那么裸的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(' ');} 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 ",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颜色
如果：
不可能更新到那个1的儿子，因为那个1的点权至少是2，所以没有问题！
然后，就成静态的了。。。。
LCT、树剖就随便做了。。。。。。