分析
假设现在有一个 1 l r x 的操作。我们考虑一下第 $l-1$ 棵树和第 $l$ 棵树、第 $r$ 棵树和第 $r+1$ 棵树的区别。这里假设只有一个这 1 操作。
我们可以这么认为：第 $l$ 棵树是把第 $l-1$ 棵树上生长节点的子树移到第 $l$ 棵树的生长节点上得到的；第 $r+1$ 棵树是把第 $r$ 棵树上生长节点的子树移回去得到的。
那么如果我们可以快速换子树的父亲就可以得到每一棵树了。
考虑添加虚点来解决问题。对于每个 1 操作，我们建一个虚点，然后把所有从它长出来的点都接在这个虚点下面。
这样子就可以通过断掉虚点与父节点的连边，再连一条边实现换父亲了。
还有一个 2 操作没有处理，考虑怎么做。
我们把所有实点的点权设为 $1$ ，虚点的点权设为 $0$ 。那么直接在 LCT 上查路径和就行了。
然而因为是有根树，所以不能 split。事实上维护树上前缀和即可。
上面讲的不是很清楚，描述一下粗略的算法过程。
我们把所有操作离线，然后先把该建的东西都建好，该连的边都连好。
然后我们按树的编号顺序访问所有的 1 操作和 2 操作。如果是 1 操作，那么改子树的父节点；如果是 2 操作，那么直接查询。
如果不是很理解的话可以结合代码画图理解一下。
代码
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') c=getchar();
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=400000+10;
//--------------------------------------
int fa[N],ch[N][2];
int val[N],sum[N];
inline int nroot(int x) { return x==ch[fa[x]][0]||x==ch[fa[x]][1]; }
inline void pushup(int x) {
sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+val[x];
}
inline void rotate(int x) {
int y=fa[x],z=fa[y],k=(x==ch[y][1]),w=ch[x][!k];
if (nroot(y)) ch[z][ch[z][1]==y]=x;
ch[x][!k]=y,ch[y][k]=w;
if (w) fa[w]=y; fa[y]=x,fa[x]=z;
pushup(y);
}
inline void splay(int x) {
while (nroot(x)) {
int y=fa[x],z=fa[y];
if (nroot(y)) rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
rotate(x);
}
pushup(x);
}
inline int access(int x) {
int y=0;
for (;x;y=x,x=fa[x])
splay(x),ch[x][1]=y,pushup(x);
return y;
}
inline void link(int x,int y) {
access(x),splay(x),fa[x]=y;
}
inline void cut(int x) {
access(x),splay(x);
ch[x][0]=fa[ch[x][0]]=0,pushup(x);
}
//--------------------------------------
struct query { int pos,tim,x,y; } q[N];
bool operator <(query a,query b) {
if (a.pos!=b.pos) return a.pos<b.pos;
else return a.tim<b.tim;
}
int n,m,Q,cnt,tot=2,real=1,grow=2;
int id[N],L[N],R[N],ans[N];
//--------------------------------------
int main() {
n=read(),m=read(); link(2,1);
val[1]=1,id[1]=1,L[1]=1,R[1]=n;
for (re int i=1;i<=m;++i) {
int op=read();
if (!op) {
int l=read(),r=read();
id[++real]=++tot,link(tot,grow);
val[tot]=1,L[real]=l,R[real]=r;
} else if (op==1) {
int l=read(),r=read(),x=read();
l=max(l,L[x]),r=min(r,R[x]);
if (l>r) continue;
++tot; link(tot,grow);
q[++cnt]=(query){l,i-m,tot,id[x]};
q[++cnt]=(query){r+1,i-m,tot,grow};
grow=tot;
} else {
int x=read(),u=read(),v=read();
q[++cnt]=(query){x,++Q,id[u],id[v]};
}
}
sort(q+1,q+cnt+1);
for (re int i=1;i<=cnt;++i) {
if (q[i].tim<0) cut(q[i].x),link(q[i].x,q[i].y);
else {
int res=0;
access(q[i].x),splay(q[i].x); res=sum[q[i].x];
int t=access(q[i].y); splay(q[i].y); res+=sum[q[i].y];
access(t),splay(t); res-=(sum[t]<<1);
ans[q[i].tim]=res;
}
}
for (re int i=1;i<=Q;++i) printf("%d\n",ans[i]);
return 0;
}