//Luogu P3203 [HNOI2010]弹飞绵羊 //Jan,9th,2018 //LCT模板题II #include<iostream> #include<cstdio> using namespace std; long long read() while(isdigit(c)) return x*f; } const int N=200000+100; int n,m; struct LCT { int son[N][2],fa[N],lazy[N],mstack[N],top,size[N]; inline bool isRoot(int x) { return x!=son[fa[x]][0] && x!=son[fa[x]][1]; } inline void update(int x) { size[x]=size[son[x][0]]+size[son[x][1]]+1; } inline void mirror(int x) { lazy[x]=!lazy[x],swap(son[x][0],son[x][1]); } inline void pushDown(int x) inline void rotate(int x,int type) void splay(int x) } void Access(int x) { for(int t=0;x!=0;t=x,x=fa[x]) splay(x),son[x][1]=t,fa[t]=x,update(x); } inline void MakeRoot(int x) { Access(x),splay(x); mirror(x); } inline void Link(int x,int y)//x翻为根连向y { MakeRoot(x); fa[x]=y; } inline void split(int x,int y)//y为根 { MakeRoot(x); Access(y),splay(y); } inline void Cut(int x,int y) { split(x,y); son[y][0]=fa[x]=0; update(y); } int Query(int x) { MakeRoot(n+1); Access(x),splay(x); return size[x]-1; } }lct; int q[N]; int main() else } return 0; }









