Description:

一棵树， $1$ 号点是根，刚开始时涂有不同颜色，三种操作：

1、将一个点到根节点涂一种新颜色。

>

2、查询 $x$ 到 $y$ 路径上的颜色数。

>

3、询问以 $k$ 为根的子树中每个点到根节点的路径上颜色数最多的点到根路径上的颜色数。

Solution:

可以发现颜色实际上是没用的，只要维护同种颜色的集合即可，发现每种颜色在树上一定是深度递增的一条链， $1$ 操作就是把这个点到根的路径划为一个集合，似乎和 $LCT$ 的 $access$ 很像，于是用 $LCT$ 的辅助树维护颜色集合，由于 $LCT$ 每次 $access$ 建一棵新树维护 $1$ 到 $k$ 的路径，所以 $1$ 操作 $=access$ ，由于用 $LCT$ 维护集合，所以 $2$ 操作不能用 $LCT$ 做，在 $dfs$ 序上建线段树维护每个点到根节点的颜色数 $cnt$ ，则 $x$ 到 $y$ 的颜色数为 $cnt_x+cnt_y-2\times cnt_{lca}+1$ ，每次 $access$ 是换重儿子的过程，以前的重儿子 $cnt$ 要加一，现在的重儿子 $cnt$ 要减一，在线段树上区间加即可，注意辅助树的根 $\ne$ 原树的根，所以要找一下子树根，不 $splay$ 直接不停找左儿子即可， $3$ 操作线段树上查最大即可。

最后还要注意建树时，为了保证 $1$ 是根，把每个点在 $LCT$ 中的 $fa$ 设成他们在原树中的 $fa$ ，这样 $1$ 就是根了。

$node$ 里只有 $fa$ 和 $ch$ 。

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

struct node

{

	int fa,c[2];

	node(){fa = c[0] = c[1] = 0;}

}t[MAXN];

int id(int x){return (t[t[x].fa].c[0] == x ? 0 : 1);}

void connect(int x,int f,int p){t[x].fa = f;t[f].c[p] = x;return;}

bool isroot(int x){return (t[t[x].fa].c[0] != x && t[t[x].fa].c[1] != x);}

void rotate(int x)

{

	register int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

	if(!isroot(y))t[z].c[fy] = x;

	t[x].fa = z;

	connect(t[x].c[fx^1],y,fx);

	connect(y,x,fx^1);

	return; 

}

void splay(int x)

{

	while(!isroot(x))

	{

		register int y = t[x].fa;

		if(isroot(y)){rotate(x);break;}

		if(id(x) == id(y)){rotate(y);rotate(x);}

		else{rotate(x);rotate(x);}

	}

}

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int dep[MAXN],fa[MAXN],siz[MAXN],top[MAXN],son[MAXN],rank[MAXN],th[MAXN],tot = 0;

void dfs1(int k,int depth)

{

	dep[k] = depth;

	siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k])

		{

			t[e[i].to].fa = k;

			fa[e[i].to] = k;

			dfs1(e[i].to,depth + 1);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

			{

				son[k] = e[i].to;

			}

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;

	rank[k] = ++tot;

	th[tot] = k;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != son[k] && e[i].to != fa[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

int LCA(int a,int b)

{

	while(top[a] != top[b])

	{

		if(dep[top[a]] < dep[top[b]])swap(a,b);

		a = fa[top[a]];

	}

	if(dep[a] > dep[b])swap(a,b);

	return a;

}

namespace segment

{

	struct node

	{

		int lc,rc,tag,maxv;

		node(){lc = rc = tag = maxv = 0;}

	}t[MAXN << 1];

	int ptr = 0;

	int newnode(){return ++ptr;}

	int root;

	void build(int &rt,int l,int r)

	{

		rt = newnode();

		if(l == r)

		{

			t[rt].maxv = dep[th[l]];

			return;

		} 

		int mid = ((l + r) >> 1);

		build(t[rt].lc,l,mid);

		build(t[rt].rc,mid + 1,r);

		t[rt].maxv = max(t[t[rt].lc].maxv,t[t[rt].rc].maxv); 

		return;

	}

	void pushdown(int rt)

	{

		if(t[rt].tag == 0)return;

		t[t[rt].lc].maxv += t[rt].tag;

		t[t[rt].lc].tag += t[rt].tag;

		t[t[rt].rc].maxv += t[rt].tag;

		t[t[rt].rc].tag += t[rt].tag;

		t[rt].tag = 0;

		return;

	}

	void add(int rt,int L,int R,int k,int l,int r)

	{

		if(L <= l && r <= R)

		{

			t[rt].tag += k;

			t[rt].maxv += k;

			return;

		}

		pushdown(rt);

		int mid = ((l + r) >> 1);

		if(L <= mid)add(t[rt].lc,L,R,k,l,mid);

		if(R >= mid + 1)add(t[rt].rc,L,R,k,mid + 1,r);

		t[rt].maxv = max(t[t[rt].lc].maxv,t[t[rt].rc].maxv);

		return;

	}

	int query(int rt,int p,int l,int r)

	{

		if(l == r)return t[rt].maxv;

		pushdown(rt);

		int mid = ((l + r) >> 1);

		if(p <= mid)return query(t[rt].lc,p,l,mid);

		else return query(t[rt].rc,p,mid + 1,r);

	}

	int askmax(int rt,int L,int R,int l,int r)

	{

		if(L <= l && r <= R)

		{

			return t[rt].maxv;

		}

		pushdown(rt);

		int mid = ((l + r) >> 1);

		int res = 0;

		if(L <= mid)res = max(res,askmax(t[rt].lc,L,R,l,mid));

		if(R >= mid + 1)res = max(res,askmax(t[rt].rc,L,R,mid + 1,r));

		return res;

	}

}

int findroot(int k)

{

	while(true){if(t[k].c[0] != 0)k = t[k].c[0];else break;}

	return k;

}

void access(int k)

{

	register int rt;

	for(int i = 0;k;i = k,k = t[k].fa)

	{

		splay(k);

		rt = findroot(t[k].c[1]);

		if(rt != 0)segment::add(segment::root,rank[rt],rank[rt] + siz[rt] - 1,1,1,n);

		t[k].c[1] = i;

		rt = findroot(t[k].c[1]);

		if(rt != 0)segment::add(segment::root,rank[rt],rank[rt] + siz[rt] - 1,-1,1,n);

	}

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	int a,b;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	dfs1(1,1);dfs2(1,1);segment::build(segment::root,1,n);

	int x,y,z;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d",&x);

		if(x == 1)

		{

			scanf("%d",&y);

			access(y);

		}

		if(x == 2)

		{

			scanf("%d%d",&y,&z);

			int lca = LCA(y,z);

			printf("%d\n",segment::query(segment::root,rank[y],1,n) + segment::query(segment::root,rank[z],1,n) - 2 * segment::query(segment::root,rank[lca],1,n) + 1); 

		}

		if(x == 3)

		{

			scanf("%d",&y);

			printf("%d\n",segment::askmax(segment::root,rank[y],rank[y] + siz[y] - 1,1,n));

		}

	}

	return 0;

}