题目描述

JOI Kingdom is an insular country consisting of $N$ islands, numbered from $1$ to $N$. The islands are connected by $N − 1$ bridges, numbered from $1$ to $N − 1$. The bridge $i\ (1 ≤ i ≤ N − 1)$ connects the island $A_i$ and the island $B_i$ bidirectionally. It is possible to travel from any island to any other island by passing through a number of bridges. In JOI Kingdom, there are $M$ sightseeing spots, numbered from $1$ to $M$. The sightseeing spot $j\ (1 ≤ j ≤ M)$ is located in the island $C_j$. There are $Q$ travelers. They plan to visit sightseeing spots in JOI Kingdom. The travelers are numbered from $1$ to $Q$. Each traveler makes a trip in the following way.

1. The traveler chooses an island $x\ (1 ≤ x ≤ N)$. Taking an airplane, the traveler arrives at the island $x$.

2. The traveler takes the following actions a number of times. The order and the kinds of actions are arbitrary.

   • The traveler chooses a sightseeing spot in the current island, and visits there.
   • The traveler moves to another island by passing through a bridge.

3. Taking an airplane, the traveler leaves JOI Kingdom. The traveler $k\ (1 ≤ k ≤ Q)$ wants to visit all of the sightseeing spots $L_k, L_{k + 1}, . . . , R_k$. However, since the budget is limited, the traveler $k$ wants to minimize the number of islands where the traveler $k$ visits at least once.

Write a program which, given information of JOI Kingdom and the travelers, calculates, for each $k\ (1 ≤ k ≤ Q)$, the minimum possible number of islands where the traveler $k​$ visits at least once.

输入格式

Read the following data from the standard input.

$N\ M\ Q$

$A_1\ B_1$

$A_2\ B_2$

$\vdots$

$A_{N−1}\ B_{N−1}$

$C_1\ C_2\ · · ·\ C_M$

$L_1\ R_1$

$L_2\ R_2$

$\vdots$

$L_Q\ R_Q$

输出格式

Write $Q$ lines to the standard output. The $k$-th line $(1 ≤ k ≤ Q)$ of output should contain the minimum possible number of islands where the traveler $k$ visits at least once.

题目大意

给出一颗 $n$ 个节点的树，和一个长度为 $m$ 的序列 $a$，$q$ 次询问包含 $a_{l\cdots r}$ 中所有节点的最小联通块大小。

$n,m,q\le 10^5$

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

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

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】

The traveler 1 makes a trip in the following way, and visits all of the sightseeing spots 1, 2, 3.

1. The traveler 1 arrives at the island 2.
2. The traveler 1 visits the sightseeing spot 1 in the island 2.
3. The traveler 1 moves from the island 2 to the island 1 by passing through the bridge 1.
4. The traveler 1 moves from the island 1 to the island 3 by passing through the bridge 2.
5. The traveler 1 visits the sightseeing spot 2 in the island 3.
6. The traveler 1 moves from the island 3 to the island 6 by passing through the bridge 5.
7. The traveler 1 visits the sightseeing spot 3 in the island 6.
8. The traveler 1 departs from the island 6 and leaves JOI Kingdom.

The islands 1, 2, 3, 6 are the four islands where the traveler 1 visits at least once. If the number of islands traveler 1 visits at least once is less than or equal to 3, it is impossible to visit all of the sightseeing spots 1, 2, 3. Therefore, output 4 in the first line. The traveler 2 makes a trip in the following way, and visits all of the sightseeing spots 4, 5, 6.

1. The traveler 2 arrives at the island 3.
2. The traveler 2 moves from the island 3 to the island 7 by passing through the bridge 6.
3. The traveler 2 visits the sightseeing spot 6 in the island 7.
4. The traveler 2 moves from the island 7 to the island 3 by passing through the bridge 6.
5. The traveler 2 moves from the island 3 to the island 1 by passing through the bridge 2.
6. The traveler 2 moves from the island 1 to the island 2 by passing through the bridge 1.
7. The traveler 2 moves from the island 2 to the island 4 by passing through the bridge 3.
8. The traveler 2 visits the sightseeing spot 4 in the island 4.
9. The traveler 2 moves from the island 4 to the island 2 by passing through the bridge 3.
10. The traveler 2 moves from the island 2 to the island 5 by passing through the bridge 4.
11. The traveler 2 visits the sightseeing spot 5 in the island 5.
12. The traveler 2 departs from the island 5 and leaves JOI Kingdom.

The islands 1, 2, 3, 4, 5, 7 are the six islands where the traveler 2 visits at least once. If the number of islands traveler 2 visits at least once is less than or equal to 5, it is impossible to visit all of the sightseeing spots 4, 5, 6. Therefore, output 6 in the second line. This sample input satisfies the constraints of Subtasks 1, 2, 4, 5, 6.

The islands 1, 2, 3, 4, 5, 7 are the six islands where the traveler 2 visits at least once. If the number of islands traveler 2 visits at least once is less than or equal to 5, it is impossible to visit all of the sightseeing spots 4, 5, 6. Therefore, output 6 in the second line.

This sample input satisfies the constraints of Subtasks 1, 2, 4, 5, 6.

【样例解释 #2】

This sample input satisfies the constraints of Subtasks 1, 2, 3, 6.

【样例解释 #3】

This sample input satisfies the constraints of Subtasks 1, 2, 6.

【数据范围】

• $1 ≤ N ≤ 100 000$.
• $1 ≤ M ≤ 100 000$.
• $1 ≤ Q ≤ 100 000$.
• $1 ≤ A_i ≤ N\ (1 ≤ i ≤ N − 1)$.
• $1 ≤ B_i ≤ N\ (1 ≤ i ≤ N − 1)$.
• It is possible to travel from any island to any other island by passing through a number of bridges.
• $1 ≤ C_j ≤ N\ (1 ≤ j ≤ M)$.
• $1 ≤ L_k ≤ R_k ≤ M\ (1 ≤ k ≤ Q)$.
• Given values are all integers.

【子任务】

1. (5 points) $N ≤ 300, M ≤ 300, Q ≤ 300$.
2. (5 points) $N ≤ 2 000, M ≤ 2 000, Q ≤ 2 000$.
3. (7 points) $A_i = i, B_i = i + 1\ (1 ≤ i ≤ N − 1)$.
4. (18 points) $L_1 = 1, R_{k} + 1 = L_{k+1}\ (1 ≤ k ≤ Q − 1), R_Q = M$.
5. (24 points) $A_i = \lfloor\frac{i+1}2\rfloor, B_i = i + 1\ (1 ≤ i ≤ N−1)$. Here, $⌊x⌋$ is the largest integer not exceeding x.
6. (41 points) No additional constraints.