#2001. 「SDOI2017」树点涂色

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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 行,表示操作,格式见题目描述。

输出格式

每当出现 23 操作,输出一行。

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

样例

样例输入

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

样例输出

3
4
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