「BalkanOI 2023 Day2」Aliens

题目描述

译自 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$ 个行星。

样例 1

输入

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

说明
只有一个起源行星，我们在游览中访问了行星 $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

输入

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 \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