PLCT检查是什么洛谷P3348 [ZJOI2016]大森林（LCT，虚点，树上差分）

  1 //minamoto
  2 #include<cstdio>
  3 #include<iostream>
  4 #include<algorithm>
  5 using std::sort;
  6 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
  7 char buf[1<<21],*p1=buf,*p2=buf;
  8 template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
  9 template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
 10 inline int read()
 20 char obuf[1<<24],*o=obuf;
 21 void print(int x)
 25 const int N=300005;
 26 #define qr(a,b,c,d) qry[++cnt]=(q){a,b,c,d}
 27 struct q{
 28     int pos,opt,x,y;
 29     inline bool operator <(const q &b)const
 30     {return pos<b.pos||(pos==b.pos&&opt<b.opt);}
 31 }qry[N];
 32 int fa[N],ch[N][2],gl[N],gr[N],sum[N],at[N],ans[N];
 33 bool v[N];
 34 inline bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
 35 #define ls ch[x][0]
 36 #define rs ch[x][1]
 37 inline void pushup(int x){sum[x]=sum[ls]+sum[rs]+v[x];}
 38 void rotate(int x)
 43 void splay(int x)
 49     pushup(x);
 50 }
 51 int access(int x){
 52     int y=0;
 53     for(;x;x=fa[y=x]){
 54         splay(x),rs=y,pushup(x);
 55     }
 56     return y;
 57 }
 58 void cut(int x){
 59     access(x),splay(x),ls=fa[ls]=0;pushup(x);
 60 }
 61 void link(int x,int y){
 62     splay(x),fa[x]=y;
 63 }
 64 int main(){
 65     //freopen("testdata.in","r",stdin);
 66     int n,m,cnt=0,tot=0,real,aux,p;
 67     n=read(),m=read();
 68     real=v[1]=sum[1]=gl[1]=at[1]=1,gr[1]=n;
 69     link(p=aux=2,1);
 70     for(int i=1;i<=m;++i){
 71         int op=read(),l=read(),r=read();
 72         switch(op){
 73             case 0:{
 74                 link(at[++real]=++p,aux),v[p]=sum[p]=1;
 75                 gl[real]=l,gr[real]=r;
 76                 break;
 77             }
 78             case 1:
 87             case 2:{
 88                 int x=read();
 89                 qr(l,++tot,at[r],at[x]);
 90                 break;
 91             }
 92         }
 93     }
 94     sort(qry+1,qry+1+cnt);
 95     for(int i=1;i<=cnt;++i)
102         else cut(qry[i].x),link(qry[i].x,qry[i].y);
103     }
104     for(int i=1;i<=tot;++i)
105     print(ans[i]),*o++='
';
106     fwrite(obuf,o-obuf,1,stdout);
107     return 0;
108 }