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\le n,m\le 100000\)

Output:


每当出现2,3操作,输出一行。
如果是2操作,输出一个数表示路径的权值;
如果是3操作,输出一个数表示权值的最大值。

Sample Input:


Sample Output:


题解:


这题可以说是最清奇的LCT了。

仔细观察,觉得1操作和access很像,于是自然想到用LCT中的一棵Splay树表示一条颜色链。(基于每一次颜色都不同)

考虑第二个和第三个操作,如果直接用LCT维护的话,可能需要维护子树信息,并且复杂度还不对,于是我们换一种思路。

用线段树维护每一个点到根的路径的权值(dfs序),第三个操作就是区间最大值。因为这道题每次染色都是一条到根的链,路径权值还满足差分,第二个操作答案就是 \(val(x)+val(y)-val(lca)\times 2 + 1\)

我们在access时,有虚边转实边就把深度大的一边子树加1,实边转虚边减1就可以了。

时间复杂度 \(O(m\log_2^2 n)\)