/ Vijos / 题库 /

树点涂色

树点涂色

描述

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

信息

ID
2014
难度
4
分类
(无)
标签
递交数
25
已通过
14
通过率
56%
被复制
2
上传者

相关

在下列训练计划中:

RP++分类题库