#1113. [SDOI2017] 树点涂色
[SDOI2017] 树点涂色
题目描述
Bob 有一棵 个点的有根树,其中 号点是根节点。Bob 在每个点上涂了颜色,并且每个点上的颜色不同。
定义一条路径的权值是:这条路径上的点(包括起点和终点)共有多少种不同的颜色。
Bob可能会进行这几种操作:
1 x
表示把点 到根节点的路径上所有的点染上一种没有用过的新颜色。2 x y
求 到 的路径的权值。3 x
在以 为根的子树中选择一个点,使得这个点到根节点的路径权值最大,求最大权值。
Bob一共会进行 次操作
输入格式
第一行两个数 。
接下来 行,每行两个数 ,表示 与 之间有一条边。
接下来 行,表示操作,格式见题目描述
输出格式
每当出现 操作,输出一行。
如果是 操作,输出一个数表示路径的权值
如果是 操作,输出一个数表示权值的最大值
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
提示
共 个测试点。
测试点 ,;
测试点 ,没有 操作;
测试点 ,没有 操作;
测试点 ,树的生成方式是,对于 ,在 中随机选一个点作为 的父节点;
测试点 ,;
测试点 ,;
测试点9,10,无特殊限制
对所有数据,,。