Problem 4817. -- [Sdoi2017]树点涂色

F.A.Qs	Home	Discuss	ProblemSet	Status	Ranklist	Contest	入门OJ	Login	Register

Problem 4817. -- [Sdoi2017]树点涂色

4817: [Sdoi2017]树点涂色

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1025 Solved: 651
[Submit][Status][Discuss]

Description

Bob有一棵n个点的有根树，其中1号点是根节点。Bob在每个点上涂了颜色，并且每个点上的颜色不同。定义一条路

径的权值是：这条路径上的点（包括起点和终点）共有多少种不同的颜色。Bob可能会进行这几种操作：

1 x:

把点x到根节点的路径上所有的点染上一种没有用过的新颜色。

2 x y:

求x到y的路径的权值。

3 x

在以x为根的子树中选择一个点，使得这个点到根节点的路径权值最大，求最大权值。

Bob一共会进行m次操作

Input

第一行两个数n,m。

接下来n-1行，每行两个数a,b，表示a与b之间有一条边。

接下来m行，表示操作，格式见题目描述

1<=n,m<=100000

Output

每当出现2,3操作，输出一行。

如果是2操作，输出一个数表示路径的权值

如果是3操作，输出一个数表示权值的最大值

Sample Input

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

Sample Output

3
4
2
2

HINT

Source

鸣谢infinityedge上传

[Submit][Status][Discuss]
HOME Back