题目
我是傻逼。
LCT和树剖LCA共用(fa)数组。
线段树的update写了个
if(R>L) return ;
首先这种链、子树操作的题一看就会想到树剖，但是第一个操作没那么好写。
如果我们把相同颜色的一段看成一个连通块的话，那么第一个操作就是一个access了。
由于“每次染一个新的颜色”和“每次染颜色的都是到根的一条链”这两个特殊性质，我们可以推导出一个非常优美的结论：
如果我们记(f_i)表示(i)到根路径上的颜色个数，那么((u,v))这条路径上的颜色个数就是(f_u+f_v-2*f_{lca(u,v)}+1)。想一想，为什么？
（同时这个性质可以保证我们树剖暴力修改的复杂度是均摊(O(log^2n))的。）
而且这个(f)它就是LCT上某个点到根节点的轻边数量(+1)。
那么我们就可以用LCT来单独维护每个颜色的连通块，然后用dfs序+线段树来维护(f)数组。
这样第一个操作就只需要在access的时候针对轻重链的变化进行子树加就行了。
第二个操作就是单点求值，第三个操作就是子树求(max)，这都可以用线段树维护。
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
namespace IO
{
char ibuf[(1<<21)+1],obuf[(1<<21)+1],st[11],*iS,*iT,*oS=obuf,*oT=obuf+(1<<21);
char Get(){return (iS==iT? (iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT? EOF:*iS++)):*iS++);}
void Flush(){fwrite(obuf,1,oS-obuf,stdout),oS=obuf;}
void Put(char x){*oS++=x;if(oS==oT)Flush();}
int read(){int x=0,c=Get();while(!isdigit(c))c=Get();while(isdigit(c))x=x*10+c-48,c=Get();return x;}
void write(int x){int top=0;while(x)st[++top]=(x%10)+48,x/=10;while(top)Put(st[top--]);Put('
');}
}
using IO::read;using IO::write;using IO::Flush;
int max(int a,int b){return a>b? a:b;}
const int N=100007;
int n,m;
namespace Tree
{
vector<int>E[N];int fa[N],st[N],id[N],ed[N],T,size[N],dep[N],son[N],top[N];
void add(int u,int v){E[u].pb(v),E[v].pb(u);}
void dfs(int u)
{
dep[id[st[u]=++T]=u]=dep[fa[u]]+(size[u]=1);
for(int v:E[u]) if(v^fa[u]) fa[v]=u,dfs(v),size[u]+=size[v],son[u]=size[v]>size[son[u]]? v:son[u];
ed[u]=T;
}
void dfs(int u,int tp)
{
top[u]=tp;
if(son[u]) dfs(son[u],tp);
for(int v:E[u]) if(v^fa[u]&&v^son[u]) dfs(v,v);
}
int lca(int u,int v)
{
while(top[u]^top[v]) dep[top[u]]>dep[top[v]]? u=fa[top[u]]:v=fa[top[v]];
return dep[u]<dep[v]? u:v;
}
}using namespace Tree;
namespace Seg
{
int mx[N<<2],tag[N<<2];
#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)>>1)
void pushup(int p){mx[p]=max(mx[ls],mx[rs]);}
void modify(int p,int v){mx[p]+=v,tag[p]+=v;}
void pushdown(int p){modify(ls,tag[p]),modify(rs,tag[p]),tag[p]=0;}
void build(int p,int l,int r)
{
if(l==r) return (void)(mx[p]=dep[id[l]]);
build(ls,l,mid),build(rs,mid+1,r),pushup(p);
}
void update(int p,int l,int r,int L,int R,int x)
{
if(L<=l&&r<=R) return modify(p,x);
if(tag[p]) pushdown(p);
if(L<=mid) update(ls,l,mid,L,R,x);
if(R>mid) update(rs,mid+1,r,L,R,x);
pushup(p);
}
int query(int p,int l,int r,int L,int R)
{
if(L<=l&&r<=R) return mx[p];
if(tag[p]) pushdown(p);
return max((L<=mid? query(ls,l,mid,L,R):0),(R>mid? query(rs,mid+1,r,L,R):0));
}
#undef ls
#undef rs
#undef mid
}using namespace Seg;
#define root 1,1,n
namespace LCT
{
int ch[N][2],f[N];
#define lc ch[x][0]
#define rc ch[x][1]
int nroot(int x){return ch[f[x]][0]==x||ch[f[x]][1]==x;}
void rotate(int x)
{
int y=f[x],z=f[y],k=ch[y][1]==x,w=ch[x][!k];
if(nroot(y))ch[z][ch[z][1]==y]=x;
ch[x][!k]=y,ch[y][k]=w,f[w]=y,f[y]=x,f[x]=z;
}
void splay(int x){for(int y;nroot(x);rotate(x)) if(nroot(y=f[x])) rotate((ch[f[y]][0]==y)^(ch[y][0]==x)? x:y);}
int findroot(int x){while(lc)x=lc;return x;}
void access(int x)
{
for(int y=0,z;x;x=f[y=x])
{
splay(x);
if(rc) z=findroot(rc),update(root,st[z],ed[z],1);
if(y) z=findroot(y),update(root,st[z],ed[z],-1);
rc=y;
}
}
#undef lc
#undef rc
}using namespace LCT;
int main()
{
n=read(),m=read();
for(int i=1,u,v;i<n;++i) u=read(),v=read(),add(u,v);
dfs(1),dfs(1,1),build(root),memcpy(f,fa,sizeof fa);
for(int x,y,l;m;--m)
switch(read())
{
case 1:access(read());break;
case 2:x=read(),y=read(),l=lca(x,y),write(query(root,st[x],st[x])+query(root,st[y],st[y])-query(root,st[l],st[l])*2+1);break;
case 3:x=read(),write(query(root,st[x],ed[x]));break;
}
return Flush(),0;
}