中等题（medium）

题目描述

给定一棵有 $n+1$ 个点的树，点的编号从 $0$ 到 $n$，保证 $n$ 是叶子。每个点有互不相同的点权 $p_i$。

额外给定除 $n$ 以外的 $k$ 个叶子。记 $S$ 为这 $k+1$ 个叶子中，任意两个叶子的路径上的点形成的集合，即这些路径上所有点的并集。

有 $q$ 次询问，询问有如下两种：

• 1：询问 $S$ 的大小。保证这类询问恰好有一个。
• 2 u d r：给定 $u,d,r$，保证 $u\in S$。问在与 $u$ 距离为 $d$ 的所有点中，点权第 $r$ 小的点是哪个。保证这样的点至少有 $r$ 个。

两点的距离定义为它们路径上边的数量。

输入格式

第一行三个正整数 $n,k,q$。

第二行 $n+1$ 个整数 $p_0,p_1,\ldots,p_n$。

第三行 $k$ 个整数，表示额外给定的叶子。

接下来 $n$ 行，每行两个整数 $u,v$，表示一条树边。

接下来的 $q$ 行，每行满足如下格式之一：

• 1，表示第一种询问。
• 2 u d r，表示第二种询问。其中 $d\ge 1$ 且 $r\ge 1$。

输出格式

对于每个询问，输出一行一个整数表示对应询问的答案。

对于第一种询问，输出 $S$ 的大小；对于第二种询问，输出对应点的编号。

样例 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

样例 1 输出

4
1
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

样例 2 输出

7
4
3
6
7
4
8
3
7
10
3

数据范围

对于所有数据：

$$1\le n,q\le 10^5,\quad 1\le k\le 10,\quad 1\le p_i\le 10^9。$$

• 子任务 1（3 分）：$q=1$。
• 子任务 2（14 分）：$n,q\le 2000$。
• 子任务 3（21 分）：$k=1$。
• 子任务 4（12 分）：$n\le 10^4$。
• 子任务 5（13 分）：$q\le 10^4$。
• 子任务 6（37 分）：无特殊限制。

@原题面