2658. [SDOI 2017] 树点涂色

【题目描述】

$Bob$ 有一棵 $n$ 个点的有根树，其中 $1$ 号点是根节点。$Bob$ 在每个节点上涂了颜色，并且每个点上的颜色不同。

定义一条路径的权值是，这条路径上的点（包括起点和终点）共有多少种不同的颜色。

$Bob$ 可能会进行这几种操作：

   $1\ x$，把点 $x$ 到根节点的路径上的所有的点染上一种没有用过的新颜色；

   $2\ x\ y$，求 $x$ 到 $y$ 的路径的权值；

   $3\ x$，在以 $x$ 为根的子树中选择一个点，使得这个点到根节点的路径权值最大，求最大权值。

$Bob$ 一共会进行 $m$ 次操作。

【输入格式】

第一行两个数 $n,m$。

接下来 $n-1$ 行，每行两个数 $a,b$，表示 $a$ 与 $b$ 之间有一条边。

接下来 $m$ 行，表示操作，格式见题目描述。

【输出格式】

每当出现 $2,3$ 操作，输出一行。

如果是 $2$ 操作，输出一个数表示路径的权值。

如果是 $3$ 操作，输出一个数表示权值的最大值。

【样例1输入】

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

【样例1输出】

3
4
2
2

【样例2】

点击下载样例2

【数据规模和约定】

测试点 $1， 1 \leq n, m \leq 1000$ ；

测试点 $2、3$，没有 $2$ 操作；

测试点 $4、5$，没有 $3$ 操作；

测试点 $6$，树的生成方式是，对于 $i （ 2 \leq i \leq n ）$，在 $i$ 到 $i - 1$ 中随机选一个点作为 $i$ 的父节点；

测试点 $7， 1 \leq n, m \leq 50000$ ；

测试点 $8， 1 \leq n \leq 50000$ ；

测试点 $9、10$，无特殊限制。

对所有数据， $1 \leq n, m \leq 10 ^ 5$ 。