看到操作1,应该学过lct的都知道这个等价于access操作,所以可以考虑用lct维护,相同颜色的一条链就用lct上的一棵splay维护,每次操作1就(access(x))
要回答操作2和操作3,都要求出某点到根的颜色段数.考虑(access(x))过程中会改变一些点的颜色段数,当某条边变成虚边后,那么对应儿子子树内所有点的颜色数都加(1),当某条边变成实边后,对应儿子子树内所有点的颜色数都减(1),这个不理解可以手动模拟access.然后操作二答案为(a_x+a_y-2*a_{lca}+1),就是两条从lca往下的链答案+lca的贡献.操作三要询问子树,但是一个点子树在(dfs)序上是连续区间,所以线段树维护每个点以及子树内答案即可
//补档
#include<bits/stdc++.h>
#define LL long long
#define il inline
#define re register
#define ldb long double
using namespace std;
const int N=100000+10;
il LL rd()
{
LL x=0,w=1;char ch;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int to[N<<1],nt[N<<1],hd[N],tot=1;
il void add(int x,int y)
{
++tot,to[tot]=y,nt[tot]=hd[x],hd[x]=tot;
++tot,to[tot]=x,nt[tot]=hd[y],hd[y]=tot;
}
int n,m,ff[N],de[N],sz[N],hson[N],top[N],dfn[N],id[N],tt;
int fa[N],ch[N][2];
void dfs1(int x)
{
sz[x]=1;
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
if(y==ff[x]) continue;
ff[y]=fa[y]=x,de[y]=de[x]+1,dfs1(y),sz[x]+=sz[y];
if(sz[hson[x]]<sz[y]) hson[x]=y;
}
}
void dfs2(int x,int ntp)
{
dfn[x]=++tt,id[tt]=x,top[x]=ntp;
if(hson[x]) dfs2(hson[x],ntp);
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
if(y==ff[x]||y==hson[x]) continue;
dfs2(y,y);
}
}
il int glca(int x,int y)
{
while(top[x]!=top[y])
{
if(de[top[x]]<de[top[y]]) swap(x,y);
x=ff[top[x]];
}
return de[x]<de[y]?x:y;
}
int ma[N<<2],lz[N<<2];
#define lc (o<<1)
#define rc ((o<<1)|1)
#define mid ((l+r)>>1)
il void psup(int o){ma[o]=max(ma[lc],ma[rc]);}
il void upd(int o,int x){ma[o]+=x,lz[o]+=x;}
il void psdn(int o)
{
if(lz[o]) upd(lc,lz[o]),upd(rc,lz[o]),lz[o]=0;
}
void bui(int o,int l,int r)
{
if(l==r) {ma[o]=de[id[l]];return;}
bui(lc,l,mid),bui(rc,mid+1,r);
psup(o);
}
void modif(int o,int l,int r,int ll,int rr,int x)
{
if(ll<=l&&r<=rr)
{
upd(o,x);
return;
}
psdn(o);
if(ll<=mid) modif(lc,l,mid,ll,rr,x);
if(rr>mid) modif(rc,mid+1,r,ll,rr,x);
psup(o);
}
int quer(int o,int l,int r,int ll,int rr)
{
if(ll<=l&&r<=rr) return ma[o];
int an=0;
psdn(o);
if(ll<=mid) an=max(an,quer(lc,l,mid,ll,rr));
if(rr>mid) an=max(an,quer(rc,mid+1,r,ll,rr));
psup(o);
return an;
}
il bool nrt(int x){return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}
il void rot(int x)
{
int y=fa[x],z=fa[y],yy=ch[y][1]==x,w=ch[x][!yy];
if(nrt(y)) ch[z][ch[z][1]==y]=x;
ch[y][yy]=w,ch[x][!yy]=y;
if(w) fa[w]=y;
fa[y]=x,fa[x]=z;
}
il void spl(int x)
{
int y,z;
while(nrt(x))
{
y=fa[x],z=fa[y];
if(nrt(y)) ((ch[y][1]==x)^(ch[z][1]==y))?rot(x):rot(y);
rot(x);
}
}
il int findrt(int x)
{
while(ch[x][0]) x=ch[x][0];
return x;
}
il void acs(int x)
{
for(int y=0,z;x;y=x,x=fa[x])
{
spl(x);
if(ch[x][1]) z=findrt(ch[x][1]),modif(1,1,n,dfn[z],dfn[z]+sz[z]-1,1);
if(y) z=findrt(y),modif(1,1,n,dfn[z],dfn[z]+sz[z]-1,-1);
ch[x][1]=y;
}
}
int main()
{
n=rd(),m=rd();
for(int i=1;i<n;++i) add(rd(),rd());
de[1]=1,dfs1(1),dfs2(1,1),bui(1,1,n);
while(m--)
{
int op=rd();
if(op==1) acs(rd());
else if(op==2)
{
int x=rd(),y=rd(),lca=glca(x,y);
printf("%d
",quer(1,1,n,dfn[x],dfn[x])+quer(1,1,n,dfn[y],dfn[y])-(quer(1,1,n,dfn[lca],dfn[lca])<<1)+1);
}
else
{
int x=rd();
printf("%d
",quer(1,1,n,dfn[x],dfn[x]+sz[x]-1));
}
}
return 0;
}