传送门
考虑到每次都是到根染上一种和原来不同的颜色 这个操作和 L C T LCT LCT时的 a c c e s s access access很像 实际询问的也就是到根改变了多少次虚实链
考虑一次 a c c e s s access access的影响 对原来的实儿子也就是多了一次切换 子树答案加1就是了 对于新的实儿子则少了一个切换 子树答案减一
树剖维护一下就完了
#include<bits/stdc++.h> using namespace std; const int RLEN=1<<20|1; inline char gc(){ static char ibuf[RLEN],*ib,*ob; (ob==ib)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin)); return (ob==ib)?EOF:*ib++; } inline int read(){ char ch=gc(); int res=0,f=1; while(!isdigit(ch))f^=ch=='-',ch=gc(); while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc(); return f?res:-res; } int n,m; const int N=100005; namespace Seg{ int tr[N<<2],add[N<<2],idx[N],dep[N]; #define lc (u<<1) #define rc ((u<<1)|1) #define mid ((l+r)>>1) inline void pushup(int u){ tr[u]=max(tr[lc],tr[rc]); } inline void pushnow(int u,int k){ tr[u]+=k,add[u]+=k; } inline void pushdown(int u){ if(!add[u])return; pushnow(lc,add[u]); pushnow(rc,add[u]); add[u]=0; } void build(int u,int l,int r){ if(l==r){tr[u]=dep[idx[l]];return;} build(lc,l,mid),build(rc,mid+1,r); pushup(u); } void update(int u,int l,int r,int st,int des,int k){ if(st<=l&&r<=des)return pushnow(u,k); pushdown(u); if(st<=mid)update(lc,l,mid,st,des,k); if(mid<des)update(rc,mid+1,r,st,des,k); pushup(u); } int query(int u,int l,int r,int st,int des){ if(st<=l&&r<=des)return tr[u]; pushdown(u); int res=0; if(st<=mid)res=max(res,query(lc,l,mid,st,des)); if(mid<des)res=max(res,query(rc,mid+1,r,st,des)); pushup(u);return res; } #undef mid #undef lc #undef rc } using namespace Seg; namespace SLPF{ int adj[N],nxt[N<<1],to[N<<1],in[N],siz[N],fa[N],top[N],son[N],dfn,cnt; inline void addedge(int u,int v){ nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v; } void dfs1(int u){ siz[u]=1; for(int e=adj[u];e;e=nxt[e]){ int v=to[e]; if(v==fa[u])continue; dep[v]=dep[u]+1,fa[v]=u; dfs1(v),siz[u]+=siz[v]; if(siz[v]>=siz[son[u]])son[u]=v; } } void dfs2(int u,int tp){ in[u]=++dfn,idx[dfn]=u,top[u]=tp; if(son[u])dfs2(son[u],tp); for(int e=adj[u];e;e=nxt[e]){ int v=to[e]; if(v==fa[u]||v==son[u])continue; dfs2(v,v); } } inline int Lca(int u,int v){ while(top[u]!=top[v]){ if(dep[top[u]]<dep[top[v]])swap(u,v); u=fa[top[u]]; } return dep[u]>dep[v]?v:u; } } using namespace SLPF; namespace Lct{ int son[N][2],f[N]; #define lc(u) son[u][0] #define rc(u) son[u][1] inline bool isrt(int u){ if(!f[u])return 1; return lc(f[u])!=u&&rc(f[u])!=u; } inline bool isrc(int u){ return rc(f[u])==u; } inline void rotate(int v){ int u=f[v],z=f[u]; int t=rc(u)==v; if(!isrt(u))son[z][rc(z)==u]=v; f[v]=z; son[u][t]=son[v][t^1],f[son[v][t^1]]=u; son[v][t^1]=u,f[u]=v; } inline void splay(int u){ while(!isrt(u)){ if(!isrt(f[u])) isrc(f[u])==isrc(u)?rotate(f[u]):rotate(u); rotate(u); } } inline int findrt(int u){ while(lc(u))u=lc(u);return u; } inline void access(int u){ for(int v=0,z;u;v=u,u=f[u]){ splay(u); if(rc(u))z=findrt(rc(u)),update(1,1,n,in[z],in[z]+siz[z]-1,1); if(rc(u)=v)z=findrt(v),update(1,1,n,in[z],in[z]+siz[z]-1,-1); } } #undef lc #undef rc } int main(){ dep[1]=1; n=read(),m=read(); for(int i=1;i<n;i++){ int u=read(),v=read(); addedge(u,v),addedge(v,u); } dfs1(1),dfs2(1,1); build(1,1,n); for(int i=1;i<=n;i++){ Lct::f[i]=fa[i]; } while(m--){ int op=read(),u=read(); if(op==1)Lct::access(u); if(op==2){ int v=read(),lca=Lca(u,v); cout<<(query(1,1,n,in[u],in[u])+query(1,1,n,in[v],in[v])-2*query(1,1,n,in[lca],in[lca])+1)<<'\n'; } if(op==3){ cout<<query(1,1,n,in[u],in[u]+siz[u]-1)<<'\n'; } } }