P9340 [JOISC 2023] Tourism (Day3)

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.

无

无

**【样例解释 #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.