#1113. [SDOI2017] 树点涂色

    ID: 1113 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数据结构线段树树结构树链剖分2017各省省选山东树剖Link-Cut TreeLCT

[SDOI2017] 树点涂色

题目描述

Bob 有一棵 nn 个点的有根树,其中 11 号点是根节点。Bob 在每个点上涂了颜色,并且每个点上的颜色不同。

定义一条路径的权值是:这条路径上的点(包括起点和终点)共有多少种不同的颜色。

Bob可能会进行这几种操作:

  • 1 x 表示把点 xx 到根节点的路径上所有的点染上一种没有用过的新颜色。
  • 2 x yxxyy 的路径的权值。
  • 3 x 在以 xx 为根的子树中选择一个点,使得这个点到根节点的路径权值最大,求最大权值。

Bob一共会进行 mm 次操作

输入格式

第一行两个数 n,mn,m

接下来 n1n-1 行,每行两个数 a,ba,b,表示 aabb 之间有一条边。

接下来 mm 行,表示操作,格式见题目描述

输出格式

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

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

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

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

提示

1010 个测试点。

测试点 111n,m10001\leq n,m\leq1000

测试点 2,32,3,没有 22 操作;

测试点 4,54,5,没有 33 操作;

测试点 66,树的生成方式是,对于 i(2in)i(2\leq i \leq n),在 1i11 \sim i-1 中随机选一个点作为 ii 的父节点;

测试点 771n,m5×1041\leq n,m\leq 5\times 10^4

测试点 881n5×1041\leq n \leq 5 \times 10^4

测试点9,10,无特殊限制

对所有数据,1n1051\leq n \leq 10^51m1051\leq m \leq 10^5