题目描述

题目译自 JOISC 2023 Day3 T3 「旅行 / Tourism」

JOI 国是一个由 $N$ 个岛屿构成的岛国，这 $N$ 个岛屿编号为 $1$ 到 $N$。这些岛屿由 $N-1$ 座桥相连，这些桥编号为 $1$ 到 $N-1$。桥 $i\ (1\le i\le N-1)$ 双向连接岛屿 $A_i$ 和 $B_i$。保证可以从一座岛屿出发，经过一定数量的桥到达任意其他岛屿。

在 JOI 国中，有 $M$ 个旅游景点，从 $1$ 到 $M$ 编号。景点 $j\ (1\le j\le M)$ 位于岛屿 $C_j$ 上。

有 $Q$ 个旅行者，编号为 $1$ 到 $Q$。他们计划去 JOI 国旅游。每个旅行者按如下方式旅游：

1. 旅行者选择一个岛屿 $x\ (1\le x\le N)$，并乘飞机抵达岛屿 $x$
2. 旅行者执行如下操作若干次，操作的顺序和种类任意
   • 旅行者选择目前岛上的一个景点并游览它
   • 旅行者通过一座桥移动到其他岛屿
3. 旅行者乘飞机离开 JOI 国

旅行者 $k\ (1\le k\le Q)$ 想要游览所有景点 $L_k,L_k+1,\ldots,R_k$。然而，由于预算有限，旅行者 $k$ 希望最小化至少去过一遍的岛屿数。

给定 JOI 国和旅行者的信息，写一个程序计算对于每个 $k\ (1\le k\le Q)$，旅行者 $k$ 至少去过一遍的岛屿数的最小值。

输入格式

第一行三个整数 $N,M,Q$。

接下来 $N-1$ 行，每行两个整数 $A_i,B_i$。

接下来一行 $M$ 个整数 $C_1,C_2,\ldots,C_M$。

接下来 $Q$ 行，每行两个整数 $L_k,R_k$。

输出格式

输出 $Q$ 行，第 $k$ 行输出一个整数，表示旅行者 $k$ 至少去过一遍的岛屿数的最小值。

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

4
6

旅行者 $1$ 按如下方式旅行，并游览景点 $1,2,3$：

1. 旅行者 $1$ 到达岛屿 $2$
2. 旅行者 $1$ 游览岛屿 $2$ 上的景点 $1$
3. 旅行者 $1$ 从岛屿 $2$ 经过桥 $1$ 到达岛屿 $1$
4. 旅行者 $1$ 从岛屿 $1$ 经过桥 $2$ 到达岛屿 $3$
5. 旅行者 $1$ 游览岛屿 $3$ 上的景点 $2$
6. 旅行者 $1$ 从岛屿 $3$ 经过桥 $5$ 到达岛屿 $6$
7. 旅行者 $1$ 游览岛屿 $6$ 上的景点 $3$
8. 旅行者 $1$ 从岛屿 $6$ 离开 JOI 国

旅行者 $1$ 至少到过一次的岛屿是岛屿 $1,2,3,6$。如果旅行者 $1$ 至少到过一次的岛屿数小于等于 $3$，就不可能游览所有景点 $1,2,3$ 了。因此第一行输出 $4$。

旅行者 $2$ 按如下方式旅行，并游览景点 $4,5,6$：

1. 旅行者 $2$ 到达岛屿 $3$
2. 旅行者 $2$ 从岛屿 $3$ 经过桥 $6$ 到达岛屿 $7$
3. 旅行者 $2$ 游览岛屿 $7$ 上的景点 $6$
4. 旅行者 $2$ 从岛屿 $7$ 经过桥 $6$ 到达岛屿 $3$
5. 旅行者 $2$ 从岛屿 $3$ 经过桥 $2$ 到达岛屿 $1$
6. 旅行者 $2$ 从岛屿 $1$ 经过桥 $1$ 到达岛屿 $2$
7. 旅行者 $2$ 从岛屿 $2$ 经过桥 $3$ 到达岛屿 $4$
8. 旅行者 $2$ 游览岛屿 $4$ 上的景点 $4$
9. 旅行者 $2$ 从岛屿 $4$ 经过桥 $3$ 到达岛屿 $2$
10. 旅行者 $2$ 从岛屿 $2$ 经过桥 $4$ 到达岛屿 $5$
11. 旅行者 $2$ 游览岛屿 $5$ 上的景点 $5$
12. 旅行者 $2$ 从岛屿 $5$ 离开 JOI 国

旅行者 $2$ 至少到过一次的岛屿是岛屿 $1,2,3,4,5,7$。如果旅行者 $2$ 至少到过一次的岛屿数小于等于 $5$，就不可能游览所有景点 $4,5,6$ 了。因此第二行输出 $6$。

这组样例满足子任务 $1,2,4,5,6$ 的限制。

8 8 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 6 4 3 5 2 4 7
3 5
4 6
6 8
1 4
2 3
6 8
5 5
2 8
1 2

3
4
6
6
3
6
1
6
3

这组样例满足子任务 $1,2,3,6$ 的限制。

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

1
6
6
4
3
1
7
5
4

这组样例满足子任务 $1,2,6$ 的限制。

数据范围与提示

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

• $1\le N,M,Q\le 10^5$
• $1\le A_i,B_i\le N$
• 保证从一座岛屿出发，可以经过一定数量的桥到达任意其他岛屿
• $1\le C_j\le N$
• $1\le L_k\le R_k\le M$

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