Description
Bob有一棵n个点的有根树，其中1号点是根节点。Bob在每个点上涂了颜色，并且每个点上的颜色不同。定义一条路
径的权值是：这条路径上的点（包括起点和终点）共有多少种不同的颜色。Bob可能会进行这几种操作：
1 x:
把点x到根节点的路径上所有的点染上一种没有用过的新颜色。
2 x y:
求x到y的路径的权值。
3 x
在以x为根的子树中选择一个点，使得这个点到根节点的路径权值最大，求最大权值。
Bob一共会进行m次操作
Input
第一行两个数n,m。
接下来n-1行，每行两个数a,b，表示a与b之间有一条边。
接下来m行，表示操作，格式见题目描述
1<=n,m<=100000
Output
每当出现2,3操作，输出一行。
如果是2操作，输出一个数表示路径的权值
如果是3操作，输出一个数表示权值的最大值
Sample Input
5 6
1 2
2 3
3 4
3 5
2 4 5
3 3
1 4
2 4 5
1 5
2 4 5
Sample Output
3
4
2
2
Sol
操作一不难看出是LCT的access操作，也就是把一个点到根全都放到一棵splay中，然后成为一个新的颜色。
对于这棵树，我们用LCT来维护所有的颜色：每条重链都是一种颜色，一个点到根的权值就是经过的轻边的个数+1。
我们还发现，这棵树的形态不会改变，所以LCT只用到了access操作，而真正存储所有点的权值是用线段树+DFS序来维护。
我们考虑如何在access操作中维护权值改变的点。
这是access时候的一般情况。我们可以发现，如果舍弃\(c[x][1]\)并且合并\(y\)的话，\(c[x][1]\)子树中的点的权值就会+1，因为多了一条轻边。\(y\)子树中的点权值会-1，因为少了一条轻边。
注意：图中标注的是某个点所在的splay！！这个点不一定是原树中对应的点！！！所以我们要做的一定是找到这个splay维护的链中深度最浅的点！！！这个暴力找或者在splay中维护都可以。
然后对于2操作，答案就是\(query(x)+query(y)-2*query(lca(x,y))+1\)，减去两次lca的权值之后，因为lca只和x或者y中的一个点颜色相同，所以再+1加回来。
对于3操作，直接用dfs序查找即可。
Code
#include <bits/stdc++.h>
#define mid ((s[x].l+s[x].r)>>1)
using namespace std;
vector<int>e[200005];
int fa[200005],c[200005][2],r[200005],o[200005],an[20][524289],dep[200005],in[200005],out[200005],rel[200005],n,m,x,y,z,op,I,a,b;
struct seg{int l,r,v,z;seg(int l=0,int r=0,int v=0,int z=0):l(l),r(r),v(v),z(z){}}s[1000005];
void dfs(int x)
{
for(int i=1;i<=17;i++) an[i][x]=an[i-1][an[i-1][x]];
in[x]=++I;rel[I]=x;
for(int i=0;i<e[x].size();i++) if(e[x][i]!=an[0][x]) an[0][e[x][i]]=x,dep[e[x][i]]=dep[x]+1,dfs(e[x][i]);
out[x]=I;
}
int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=17;~i;i--) if(dep[an[i][x]]>=dep[y]) x=an[i][x];
if(x==y) return x;
for(int i=17;~i;i--) if(an[i][x]!=an[i][y]) x=an[i][x],y=an[i][y];
return an[0][x];
}
int build(int x,int L,int R)
{
s[x]=seg(L,R,0,0);
if(L==R) return s[x].v=dep[rel[L]];
return s[x].v=max(build(x*2,L,mid),build(x*2+1,mid+1,R));
}
void down(int x){s[x*2].v+=s[x].z;s[x*2].z+=s[x].z;s[x*2+1].v+=s[x].z;s[x*2+1].z+=s[x].z;s[x].z=0;}
int query(int x,int L,int R)
{
down(x);
if(L<=s[x].l&&s[x].r<=R) return s[x].v;
return max(L<=mid?query(x*2,L,R):0,R>mid?query(x*2+1,L,R):0);
}
void update(int x,int L,int R,int V)
{
down(x);
if(L<=s[x].l&&s[x].r<=R){s[x].v+=V;s[x].z+=V;return;}
if(L<=mid) update(x*2,L,R,V);if(R>mid) update(x*2+1,L,R,V);
s[x].v=max(s[x*2].v,s[x*2+1].v);
}
void upd(int x,int v){if(x) update(1,in[x],out[x],v);}
bool R(int x,int y){return c[x][1]==y;}
bool rt(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;}
void up(int x){if(c[x][0]) o[x]=o[c[x][0]];else o[x]=x;}
void ro(int x)
{
int y=fa[x],z=fa[y],a=R(y,x),b=!a;
if(!rt(y)) c[z][R(z,y)]=x;
fa[x]=z;fa[y]=x;fa[c[x][b]]=y;c[y][a]=c[x][b];c[x][b]=y;up(y);up(x);
}
void spl(int x){for(int y=fa[x],z=fa[y];!rt(x);ro(x),y=fa[x],z=fa[y])if(!rt(y))ro(R(z,y)^R(y,x)?y:x);}
void acs(int x){for(int y=0;x;y=x,x=fa[x]) spl(x),upd(o[c[x][1]],1),upd(o[y],-1),c[x][1]=y,up(x);}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++) scanf("%d%d",&a,&b),e[a].push_back(b),e[b].push_back(a);
dep[1]=1;dfs(1);build(1,1,n);
for(int i=1;i<=n;i++) o[i]=i,fa[i]=an[0][i];
for(int i=1;i<=m;i++)
{
scanf("%d",&op);
if(op==1) scanf("%d",&x),acs(x),spl(x);
if(op==2) scanf("%d%d",&x,&y),z=lca(x,y),printf("%d\n",query(1,in[x],in[x])+query(1,in[y],in[y])-2*query(1,in[z],in[z])+1);
if(op==3) scanf("%d",&x),printf("%d\n",query(1,in[x],out[x]));
}
}