← 返回题目列表

Codeforces · 696/E

E. ...等等...

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

巴尼正在寻找他的梦中情人。他住在纽约。纽约市有 n 个路口,编号从 1 到 n,并且有 n - 1 条道路连接它们。我们将 NYC 视为一棵有根树,根为交汇处 1。 m 个女孩住在纽约,其中 i 个女孩住在交汇处 ci ,她的体重最初等于 i 磅。

Barney 认为女孩 x 比女孩 y 更好,当且仅当:女孩 x 的权重严格小于女孩 y,或者女孩 x 和女孩 y 的权重相等,并且女孩 x 的生活交界指数严格小于女孩 y 的生活交界指数,即 cx < cy。因此,对于任何两个女孩来说,其中一个总是比另一个更好。

在接下来的 q 天里,每天都会发生一个事件。有两种类型的事件:

1. Barney 从交叉路口 v 前往交叉路口 u。结果,他在路上的路口最多挑选了k个他还没有邀请的最好的女孩,邀请她们到他家来测试其中一个是否是他的梦中情人。如果他的路上有少于 k 个未邀请的女孩,他会邀请所有女孩。
2. 住在交汇点 v 子树(包括 v 本身)的交汇处的女孩体重增加了一些。结果,他们的重量增加了 k 磅。

你的任务是对于每个第一类型的事件,告诉巴尼他将在该事件中邀请到他家的女孩的索引。

输入

输入的第一行包含三个整数 n、m 和 q (1 ≤ n, m, q ≤ 105)——分别是纽约市的路口数量、居住在纽约市的女孩数量和事件数量。

接下来的 n - 1 行描述道路。每行包含两个整数 v 和 u (1 ≤ v, u ≤ n, v ≠ u),这意味着有一条道路连接交叉点 v 和 u 。

下一行包含 m 个整数 c1, c2, ..., cm (1 ≤ ci ≤ n) — 女孩的生活交汇点。

接下来的 q 行按时间顺序描述事件。每行以整数 t (1 ≤ t ≤ 2) 开头——事件的类型。

如果 t = 1,则该行描述了第一种类型的三个整数 v、u 和 k (1 ≤ v、u、k ≤ n) 的事件 — Barney 路径的端点以及他最多会邀请的女孩数量。

否则,该行描述了第二种类型的事件,后面跟着两个整数 v 和 k (1 ≤ v ≤ n, 1 ≤ k ≤ 109) — 子树的根以及子树中所有女孩的权重应增加的值。

输出

对于第一种类型的每个事件,在一行中打印数字 t,然后打印 t 个整数 g1, g2, ..., gt,这意味着在该事件中 Barney 将根据 Barney 的考虑从最好到最差的顺序邀请 t 个指数为 g1, ..., gt 的女孩。

示例

输入 #1

5 7 11
3 5
2 3
4 3
1 4
4 1 4 5 4 1 4
2 4 3
1 2 1 2
1 4 2 1
2 2 10
2 1 10
1 2 4 1
1 2 3 4
2 5 2
2 4 9
1 3 5 2
1 1 2 3

输出 #1

2 2 1
1 3
1 5
0
1 4
2 6 7

注意

对于第一个示例案例:

事件描述:

1. 连接点 4 子树中女孩的权重增加 3。这些女孩的 ID 为:1, 3, 5, 4, 7。
2. Barney 从路口 2 到路口 1。路上的女孩的 ID 为 1, 2, 3, 5, 6, 7,权重分别为 4, 2, 6, 8, 6, 10。所以,他邀请了女孩 2 和 1。
3. Barney 从 4 号路口前往 2 号路口。路上的女孩的 ID 分别为 3、 5、 7,权重分别为 6、 8、 10。所以他邀请了女孩3。
4. 连接点2子树中女孩的权重增加10。没有未邀请的女孩,所以没有任何反应。
5. 连接点 1 子树中女孩的权重增加 10。这些女孩(剩下的所有女孩)的 ID 为:4、 5、 6、 7。
6. Barney 从 2 号路口走到 4 号路口。路上的女孩的 ID 分别为 5、 7,权重分别为 18、 20。于是他邀请了5号女孩。
7. Barney 从 2 号路口前往 3 号路口。路上没有女孩。
8. 连接点 5 子树中女孩的权重增加 2。唯一的女孩是 ID 为 4 的女孩。
9. 连接点 4 子树中女孩的权重增加了 9。这些女孩的 ID 为:4、 6、 7。
10. Barney 从 3 号路口前往 5 号路口。路上唯一的女孩是 ID 为 4 的女孩。
11. Barney 从路口 1 前往路口 2。路上的女孩的 ID 分别为 6、 7,权重分别为 16、 29。