解题思路
跟重组病毒这道题很像。只是有了一个询问\(2\)的操作，然后询问\(2\)的答案其实就是\(val[x]+val[y]-2*val[lca(x,y)]+1\)(画图理解)。剩下的操作跟那道题就一样了。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN = 100005;
inline int rd(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
int n,m,head[MAXN],cnt,to[MAXN<<1],nxt[MAXN<<1];
int dep[MAXN],siz[MAXN],fa[MAXN],Fa[MAXN],L[MAXN];
int top[MAXN],id[MAXN],wt[MAXN],num,son[MAXN];
int Max[MAXN<<2],ll[MAXN],tag[MAXN<<2];
inline int max(int x,int y){
return x>y?x:y;
}
inline void add(int bg,int ed){
to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;
}
void dfs1(int x,int f,int d){
fa[x]=f;siz[x]=1;dep[x]=d;ll[x]=x;Fa[x]=f;
int maxson=-1,u;
for(int i=head[x];i;i=nxt[i]){
u=to[i];if(u==f) continue;
dfs1(u,x,d+1);siz[x]+=siz[u];
if(siz[u]>maxson) {maxson=siz[u];son[x]=u;}
}
}
void dfs2(int x,int topf){
top[x]=topf;id[x]=++num;wt[num]=dep[x];
if(!son[x]) return;dfs2(son[x],topf);int u;
for(int i=head[x];i;i=nxt[i]){
u=to[i];if(u==son[x] || u==fa[x]) continue;
dfs2(u,u);
}
}
inline void pushdown(int x){
Max[x<<1]+=tag[x];Max[x<<1|1]+=tag[x];
tag[x<<1]+=tag[x];tag[x<<1|1]+=tag[x];
tag[x]=0;
}
void build(int x,int l,int r){
if(l==r) {Max[x]=wt[l];return;}int mid=(l+r)>>1;
build(x<<1,l,mid);build(x<<1|1,mid+1,r);
Max[x]=max(Max[x<<1],Max[x<<1|1]);
}
void update(int x,int l,int r,int L,int R,int k){
if(L<=l && r<=R) {
Max[x]+=k;tag[x]+=k;
return ;
}int mid=(l+r)>>1;if(tag[x]!=0) pushdown(x);
if(L<=mid) update(x<<1,l,mid,L,R,k);
if(mid<R) update(x<<1|1,mid+1,r,L,R,k);
Max[x]=max(Max[x<<1],Max[x<<1|1]);
}
inline int lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]]) x=Fa[top[x]];
else y=Fa[top[y]];
}
return dep[x]<dep[y]?x:y;
}
int query(int x,int l,int r,int L){
if(l==r) return Max[x];
int mid=(l+r)>>1;if(tag[x]!=0) pushdown(x);
if(L<=mid) return query(x<<1,l,mid,L);
else return query(x<<1|1,mid+1,r,L);
}
inline int qRange(int x,int y){
return query(1,1,n,id[x])+query(1,1,n,id[y])-2*query(1,1,n,id[lca(x,y)])+1;
}
int query_max(int x,int l,int r,int L,int R){
if(L<=l && r<=R) return Max[x];
int mid=(l+r)>>1,ret=0;if(tag[x]!=0) pushdown(x);
if(L<=mid) ret=max(ret,query_max(x<<1,l,mid,L,R));
if(mid<R) ret=max(ret,query_max(x<<1|1,mid+1,r,L,R));
return ret;
}
inline int qSon(int x){
return query_max(1,1,n,id[x],id[x]+siz[x]-1);
}
namespace lct{
int ch[MAXN][2];
inline bool isroot(int x){
return (x!=ch[fa[x]][0] && x!=ch[fa[x]][1]);
}
inline bool check(int x){
return (x==ch[fa[x]][1]);
}
inline void pushup(int x){
if(ch[x][0]) ll[x]=ll[ch[x][0]];
else ll[x]=x;
}
inline void rotate(int x){
int y=fa[x],z=fa[y];bool chk=check(x);
if(!isroot(y)) ch[z][check(y)]=x;
ch[y][chk]=ch[x][chk^1];fa[ch[x][chk^1]]=y;
ch[x][chk^1]=y;fa[y]=x;fa[x]=z;pushup(y);pushup(x);
}
inline void splay(int x){
for(;!isroot(x);rotate(x))
if(!isroot(fa[x])) rotate(check(x)==check(fa[x])?fa[x]:x);
}
inline void access(int x){
for(int y=0;x;y=x,x=fa[x]){
splay(x);
if(y) update(1,1,n,id[ll[y]],id[ll[y]]+siz[ll[y]]-1,-1);
if(ch[x][1]) update(1,1,n,id[ll[ch[x][1]]],id[ll[ch[x][1]]]+siz[ll[ch[x][1]]]-1,1);
ch[x][1]=y;pushup(x);
}
}
}
int main(){
n=rd(),m=rd();int x,y,opt;
for(int i=1;i<n;i++){
x=rd(),y=rd();
add(x,y);add(y,x);
}
dfs1(1,0,1);dfs2(1,1);build(1,1,n);
while(m--){
opt=rd();x=rd();
if(opt==1) lct::access(x);
if(opt==2) y=rd(),printf("%d\n",qRange(x,y));
if(opt==3) printf("%d\n",qSon(x));
}
return 0;
}