题目名称 2658. [SDOI 2017] 树点涂色
输入输出 sdoi2017paint.in/out
难度等级 ★★★☆
时间限制 1000 ms (1 s)
内存限制 256 MB
测试数据 10 简单对比
题目来源 2018-04-19
开放分组 全部用户
提交状态
分类标签
通过:2, 提交:2, 通过率:100%
GravatarAAAAAAAAAA 100 1.655 s C++
GravatarShirry 100 2.117 s C++
关于 树点涂色 的讨论
数据已添加
GravatarAAAAAAAAAA
2018-04-19 16:51 1楼
这题真是太毒瘤了 > ,<
GravatarShirry
2018-04-20 20:01 2楼

2658. [SDOI 2017] 树点涂色

★★★☆   输入文件:sdoi2017paint.in   输出文件:sdoi2017paint.out   简单对比
时间限制:1 s   内存限制:256 MB

【题目描述】

Bob有一棵n个点的有根树,其中1号点是根节点。Bob在每个点上涂了颜色,并且每个点上的颜色不同。定义一条路
径的权值是:这条路径上的点(包括起点和终点)共有多少种不同的颜色。Bob可能会进行这几种操作:
1 x:把点x到根节点的路径上所有的点染上一种没有用过的新颜色。
2 x y:求x到y的路径的权值。
3 x y:在以x为根的子树中选择一个点,使得这个点到根节点的路径权值最大,求最大权值。
Bob一共会进行m次操作

【输入格式】

第一行两个数n,m。
接下来n-1行,每行两个数a,b,表示a与b之间有一条边。
接下来m行,表示操作,格式见题目描述
1<=n,m<=100000

【输出格式】

每当出现2,3操作,输出一行。
如果是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