http://www.lydsy.com/JudgeOnline/problem.php?id=4573
https://www.luogu.org/problemnew/show/P3348#sub
http://uoj.ac/problem/195
https://loj.ac/problem/2092
小Y家里有一個大森林，里面有n棵樹，編號從1到n。一開始這些樹都只是樹苗，只有一個節點，標號為1。這些樹都有一個特殊的節點，我們稱之為生長節點，這些節點有生長出子節點的能力。
小Y掌握了一種魔法，能讓第l棵樹到第r棵樹的生長節點長出一個子節點。同時她還能修改第l棵樹到第r棵樹的生長節點。她告訴了你她使用魔法的記錄，你能不能管理她家的森林，并且回答她的詢問呢？
參考：http://www.sigongzi.org/index.php/archives/LOJ2092.html
思路：
顯然我們不能對每棵樹LCT維護一下，而且我們對于這棵樹的形態還很嚴格。
那么我們把前一棵樹的形態轉換為后一棵樹的形態，這樣就只需要一棵樹了。
先考慮對于0操作，實際上我們可以記錄每個時刻每個節點在哪一段區間中（代碼的L和R就是干這個的），所以我們大可以對所有的樹都進行0操作。
對于1操作，和0操作類似，用L和R更新l和r后進行操作。
然后為了能夠快捷的更新樹，我們建立一個size為0的虛點（這樣對于路徑長度就不需要修改了），所有的生長操作都在上面進行，這樣我們刪除的時候cut這個點即可。
對于2操作，事實上兩個點一定存在的話，完全可以讓0和1操作全部排到它的前面。
實現：
先把所有操作存下來，然后以操作的樹為第一關鍵字，操作編號和順序為第二關鍵字排序。
（對于區間修改思考差分，畢竟我們都是對同一棵樹操作的。）
然后按樹編號從左到右進行操作，對于0和1操作先對虛點清空然后長即可。
查詢的時候就是用LCA求最短路的方法一樣。
#include<algorithm> #include<iostream> #include<cstring> #include<cctype> #include<cstdio> #include<vector> #include<queue> #include<cmath> using namespace std; const int N=4e5+5; struct data{int pos,id,from,to; }qry[N]; int n,m,fa[N],tr[N][2],val[N],size[N]; int cnt,tot,sum,aux,L[N],R[N],id[N],ans[N]; inline bool cmp(data a,data b){return a.pos<b.pos||(a.pos==b.pos&&a.id<b.id); } inline int read(){int X=0,w=0;char ch=0;while(!isdigit(ch)){w|=ch=='-';ch=getchar();}while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline bool get(int x){return tr[fa[x]][1]==x; } inline bool isroot(int x){if(!fa[x])return 1;return tr[fa[x]][0]!=x&&tr[fa[x]][1]!=x; } inline void upt(int x){size[x]=val[x];if(tr[x][0])size[x]+=size[tr[x][0]];if(tr[x][1])size[x]+=size[tr[x][1]]; } inline void rotate(int x){int y=fa[x],z=fa[y],b=tr[y][0]==x?tr[x][1]:tr[x][0];if(z&&!isroot(y))(tr[z][0]==y?tr[z][0]:tr[z][1])=x;fa[x]=z;fa[y]=x;b?fa[b]=y:0;if(tr[y][0]==x)tr[x][1]=y,tr[y][0]=b;else tr[x][0]=y,tr[y][1]=b;upt(y);upt(x); } inline void splay(int x){while(!isroot(x)){if(!isroot(fa[x]))rotate((get(x)==get(fa[x])?fa[x]:x));rotate(x);}upt(x); } inline int access(int x){int y;for(y=0;x;y=x,x=fa[x]){splay(x);tr[x][1]=y;if(y)fa[y]=x;}return y; } inline void link(int x,int y){splay(y);fa[x]=y; } inline void cut(int x){access(x);splay(x);if(tr[x][0])fa[tr[x][0]]=0;tr[x][0]=0;upt(x); } inline void makenode(int x){val[++sum]=x;size[sum]=x; } int main(){n=read(),m=read();cnt=1;L[cnt]=1,R[cnt]=n;id[cnt]=1;makenode(1);makenode(0);aux=sum;link(aux,id[1]);for(int i=1;i<=m;i++){int op=read();if(op==0){L[++cnt]=read(),R[cnt]=read();makenode(1);id[cnt]=sum;qry[++tot]=(data){1,i-m,sum,aux};}if(op==1){int l=read(),r=read(),x=read();l=max(l,L[x]);r=min(r,R[x]);if(l<=r){makenode(0);link(sum,aux);qry[++tot]=(data){l,i-m,sum,id[x]};qry[++tot]=(data){r+1,i-m,sum,aux};aux=sum;}}if(op==2){int l=read(),u=read(),v=read();qry[++tot]=(data){l,i,id[u],id[v]};}}memset(ans,-1,sizeof(ans));sort(qry+1,qry+tot+1,cmp);for(int i=1,p=1;i<=tot;p++){while(qry[i].pos==p){if(qry[i].id>0){ans[qry[i].id]=0;access(qry[i].from);splay(qry[i].from);ans[qry[i].id]+=size[qry[i].from];int lca=access(qry[i].to);splay(qry[i].to);ans[qry[i].id]+=size[qry[i].to];access(lca);splay(lca);ans[qry[i].id]-=size[lca]*2;}else{cut(qry[i].from);link(qry[i].from,qry[i].to);}i++;}}for(int i=1;i<=m;i++){if(ans[i]>=0)printf("%d\n",ans[i]);}return 0; }
+++++++++++++++++++++++++++++++++++++++++++
?+本文作者：luyouqi233。 +
?+歡迎訪問我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++
)
