题目描述

译自 BalkanOI 2023 Day2 T3「Aliens」

马里博尔刚刚被外星人拜访了！他们与你分享了他们的技术和历史。

有 $N+1$ 个行星，从 $0$ 到 $N$ 编号，地球的编号为 $N$。每个行星都有一个唯一的人口数 $P_{i}\ (0\leq i\leq N)$。行星之间用 $N$ 个双向传送门连接，你可以只用这些传送门在任意两个行星之间旅行。传送门 $i$（$0\leq i\leq N-1$）连接了行星 $U_{i}$ 和 $V_{i}$。两个行星之间的距离是旅行所需的最少传送门数。

你从地球出发，想要去游览 $K$ 个其他行星 $A_{0}, A_{1}, \ldots, A_{K-1}$。这些被称为起源行星。每个起源行星和地球只有一个传送门连接。你的旅程为从地球出发，访问所有起源行星以及沿途所有行星的最短路线。令 $S$ 为所有访问过的行星的集合。

现在，外星人决定通过向你提问 $Q$ 个以下两种类型的问题来测试地球是否有资格加入他们的超级文明：

• 类型 $1$：集合 $S$ 的大小是多少？
• 类型 $2$：他们从 $S$ 中选出一个行星 $x$，一个距离 $d$，和一个数字 $r$。他们问你，在距离 $x$ 为 $d$ 的行星中，按人口数从小到大排列的第 $r$ 个行星是哪个。（例如，如果 $r=1$ 答案就是距离 $x$ 为 $d$ 的星球中人口数最少的行星。这个行星可以也可以不属于集合 $S$。）

只有一个类型 $1$ 的查询。

输入格式

第一行包含三个整数 $N, K, Q$。

第二行包含 $N+1$ 个整数 $P_{0}, \ldots, P_{N}$。

第三行包含 $K$ 个整数 $A_{0}, \ldots, A_{K-1}$。

接下来的 $N$ 行中的第 $i\ (1\leq i\leq N-1)$ 行包含两个整数 $U_{i}$ 和 $V_{i}$。

接下来的 $Q$ 行满足以下格式之一：

• $1$ 表示一个类型 $1$ 的查询；
• $2\,x\,d\,r$ 表示一个类型 $2$ 的查询。

输出格式

对于每个查询，输出一行。对于类型 $1$ 的查询，输出游览期间访问的行星数；对于类型 $2$ 的查询，输出距离 $x$ 为 $d$ 的行星中按人口数排列的第 $r$ 个行星。

5 1 5
8 7 9 4 16 12
1
0 4
3 1
2 4
5 4
4 3
1
2 4 2 1
2 3 2 1
2 4 1 3
2 5 2 3

4
1
0
2
2

10 2 11
1 2 3 4 5 6 7 8 9 10 11
9 3
5 8
2 7
3 4
6 8
0 1
2 9
5 2
4 5
7 10
1 2
1
2 5 1 2
2 5 2 2
2 5 2 3
2 5 2 4
2 9 3 2
2 9 3 3
2 9 4 1
2 2 1 3
2 2 2 4
2 2 3 1

7
4
3
6
7
4
8
3
7
10
3

提示

样例 1 解释

只有一个起源行星，我们在游览中访问了行星 $S=\{1,3,4,5\}$。类型 $2$ 的查询有：

• $x=4, d=2, r=1$
• 距离行星 $4$ 为 $2$ 的只有行星 $1$。
• $x=3, d=2, r=1$
• 距离行星 $3$ 为 $2$ 的有行星 $0,2,5$。其中，行星 $0$ 的人口数最少。
• $x=4, d=1, r=3$
• 距离行星 $4$ 为 $1$ 的有行星 $0,2,3,5$，它们按人口数的顺序是 $3,0,2,5$。其中第三个是行星 $2$。
• $x=5, d=2, r=3$
• 距离行星 $5$ 为 $2$ 的有行星 $0,2,3$，它们按人口数的顺序是 $3,0,2$。其中第三个是行星 $2$。

样例 2 解释

数据范围

对于所有输入数据，满足：

• $1 \leq N \leq 10^5$
• $1 \leq K \leq 10$
• $1 \leq Q \leq 10^5$
• $1 \leq P_{i} \leq 10^{9}\ (0 \leq i \leq N)$；
• 所有的 $P_{i}$ 都是不同的
• $0 \leq A_{i} \leq N-1\ (0 \leq i \leq K-1)$
• $0 \leq U_{i}, V_{i} \leq N\ (0 \leq i \leq N-1)$
• $K$ 个起源行星和地球只有一个传送门连接
• 对于每个类型 $2$ 的查询，满足 $x \in S, d \geq 1$，且 $r \geq 1$
• 保证距离 $x$ 为 $d$ 的行星至少有 $r$ 个

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
$1$	$Q=1$	$3$
$2$	$N \leq 2000, Q \leq 2000$	$14$
$3$	$K=1$	$21$
$4$	$N \leq 10000$	$12$
$5$	$Q \leq 10000$	$13$
$6$	无附加限制	$37$