树点涂色
描述
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
样例输入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
限制
共10个测试点。
测试点1:\(1\le n,m\le 1000\)
测试点2,3:没有2操作
测试点4,5:没有3操作
测试点6:树的生成方式是,对于i(\(2\le i\le n\)),在1到\((i-1)\)中随机选一个点作为\(i\)的父节点。
测试点7:\(1\le n,m\le 50000\)
测试点8:\(1\le n\le 50000\)
测试点9,10:无特殊限制
对所有数据:\(1\le n,m\le 10^5\)
来源
SDOI 2017 Round1 Day1