← 返回题目列表

Codeforces · 414/E

E. Mashmokh 的设计问题

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

经过多次尝试,Mashmokh 设计了一个问题,你的工作就是解决它。

你有一棵有 n 个顶点的树 T。每个顶点都有一个从 1 到 n 的唯一索引。 T 的根的索引为 1。对于该树 v 的每个顶点,都会按特定顺序给出其子节点的列表。您必须对此树执行三种类型的查询:

1.求u和v之间的距离(最短路径中的边数);
2.给定v和h,断开v与其父亲的连接并将其连接到其第h个祖先;更正式地,我们用 x1, x2, ..., xl (h < l) 表示从 v 到根的路径,因此 x1 = v 并且 xl 是根;将 v 与其父 (x2) 断开并将其连接到 xh + 1;顶点 v 必须添加到顶点 xh + 1 的子列表的末尾;
3. 在调用函数 dfs(root) 产生的顶点序列中,找到距根的距离为 k 的最新顶点。

函数dfs(v)的伪代码:

输入

输入的第一行包含两个空格分隔的整数 n、m (2 ≤ n ≤ 105; 1 ≤ m ≤ 105)、T 的顶点数和要执行的查询数。

以下 n 行中的第 i 行包含一个整数 li (0 ≤ li ≤ n),即第 i 个顶点的子节点数。然后是 li 个空格分隔的整数,其中第 j 个是第 i 个顶点的第 j 个子节点的索引。请注意,这些顶点的顺序很重要。

以下 m 行中的每一行都具有以下格式之一:“1 v u”、“2 v h”或“3 k”。行中的第一个数字是根据问题陈述执行的查询类型。接下来的数字是查询的描述。

保证所有查询都是正确的。例如,在第二类查询中,h 与根的距离至少为 2,且至多为 v。同样,在第三种类型的查询中,在给出查询时,至少有一个距根的距离为 k 的顶点。

输出

对于第一或第三类型的每个查询,输出一行包含查询结果。

示例

输入 #1

4 9
1 2
1 3
1 4
0
1 1 4
2 4 2
1 3 4
3 1
3 2
2 3 2
1 1 2
3 1
3 2

输出 #1

3
2
2
4
1
3
4

输入 #2

2 2
1 2
0
1 2 1
3 1

输出 #2

1
2