← 返回题目列表

Codeforces · 1137/F

F. 比赛不是儿戏

中文机器翻译题面 查看原题

莉娜正在玩火柴。任何玩火柴的孩子脑海中自然会出现一个问题:是否可以用火柴点燃一棵树。

假设树是一个无环的连通图,顶点用整数 $$$1, 2, \ldots, n$$$ 标记。此外,每个顶点 $$$v$$$ 都有一些与其关联的整数优先级 $$$p_v$$$。所有优先事项都是不同的。

事实证明,如果你放火烧一棵树,它就会烧成灰烬。然而,这个过程不会立即发生。一开始,烧掉优先级最低的树的叶子(如果一个顶点只有一个相邻顶点,则称为叶子)。然后烧掉剩余树的最小优先级的叶子,依此类推。这样,顶点就会变成树叶并被烧毁,直到只剩下一个顶点。然后这个顶点也会被烧毁。

Lena 准备了一棵由 $$$n$$$ 顶点组成的树,其中的每个顶点都有一个优先级 $$$p_v = v$$$。莉娜对烧掉这棵树很好奇。但她明白,如果她现在就烧掉这棵树,那么它就会彻底消失。莉娜是一个善良的女孩,她会为被烧毁的树感到难过,所以她想只在脑海中研究烧毁树的过程。 Lena 想要处理 $$$q$$$ 查询,每个查询都是以下三种类型之一:

- "up $$$v$$$",指定顶点$$$v$$$优先级$$$1 + \max\{p_1, p_2, \ldots, p_n\}$$$;
- “当$$$v$$$”时,如果树现在被点燃,找到顶点$$$v$$$将烧毁的步骤;
- “比较$$$v$$$ $$$u$$$”,找出如果树现在着火的话,$$$v$$$ 和 $$$u$$$ 哪个顶点会首先烧毁。

请注意,如果所有优先级都是不同的,那么在“up”查询之后它们也将保持不同。最初,所有优先级都是不同的,因此在树的任何(当然纯粹是假设的)燃烧过程中,所有叶子都将具有不同的优先级。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$2 \le n \le 200\,000$$$, $$$1 \le q \le 200\,000$$$) - 树中的顶点数和查询数。

以下 $$$n - 1$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$v_i$$$、$$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$),表示第 $$$i$$$ 条边的端点。

其余 $$$q$$$ 行均包含以下三种类型之一的查询:

- "up $$$v$$$" ($$$1 \le v \le n$$$) — 更改顶点 $$$v$$$ 的优先级;
- "when $$$v$$$" ($$$1 \le v \le n$$$) — 确定顶点 $$$v$$$ 烧坏的步骤;
- “比较 $$$v$$$ $$$u$$$” ($$$1 \le v, u \le n$$$, $$$v \ne u$$$) - 确定 $$$v$$$ 和 $$$u$$$ 中哪个顶点将在当前树中较早烧毁。

保证至少有一个“when”或“compare”类型的查询。

输出

对于“when”类型的每个查询,打印一个从 $$$1$$$ 到 $$$n$$$ 范围内的整数 - 顶点 $$$v$$$ 将烧毁的步骤。

对于“比较”类型的每个查询,打印 $$$v$$$ 或 $$$u$$$,具体取决于哪个查询会更早耗尽。

示例

输入 #1

5 7
1 5
1 2
1 3
4 3
when 1
when 2
when 3
when 4
when 5
compare 2 3
compare 3 4

输出 #1

4
1
3
2
5
2
4

输入 #2

5 5
1 5
1 2
1 3
4 3
up 1
compare 2 4
compare 4 3
compare 3 1
compare 1 5

输出 #2

2
4
3
5

注意

在第一个示例中,树木的燃烧过程如下图所示:

特别是,树的顶点将按以下顺序烧毁:$$$[2, 4, 3, 1, 5]$$$。

在第二个示例中,应用“向上”操作后,顶点顺序将更改为:$$$[2, 4, 3, 5, 1]$$$。