2023-sp_Tourism (JOI JOI_spring)
Time limit: 4 seconds | Memory limit: 1024 MB | Task type: batch
Algorithms: mo's algorithm, lowest common ancestor, range queries, tree

![](_page_0_Picture_0.jpeg)

# Tourism

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<sub>i</sub>* and the island *B<sub>i</sub>* 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<sub>j</sub>*.

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<sub>k</sub>*, *L<sub>k</sub>* + 1, ..., *R<sub>k</sub>*. 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.

![](_page_1_Picture_0.jpeg)

## Input

Read the following data from the standard input.

```
N M Q
A1 B1
A2 B2
:
AN-1 BN-1
C1 C2 · · · CM
L1 R1
L2 R2
:
LQ RQ
```

## Output

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.

## Constraints

*   1 ≤ *N* ≤ 100 000.
*   1 ≤ *M* ≤ 100 000.
*   1 ≤ *Q* ≤ 100 000.
*   1 ≤ *A<sub>i</sub>* ≤ *N* (1 ≤ *i* ≤ *N* − 1).
*   1 ≤ *B<sub>i</sub>* ≤ *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<sub>j</sub>* ≤ *N* (1 ≤ *j* ≤ *M*).
*   1 ≤ *L<sub>k</sub>* ≤ *R<sub>k</sub>* ≤ *M* (1 ≤ *k* ≤ *Q*).
*   Given values are all integers.

![](_page_2_Picture_0.jpeg)

## Subtasks

*   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<sub>i</sub>* = *i*, *B<sub>i</sub>* = *i* + 1 (1 ≤ *i* ≤ *N* − 1).
*   4.  (18 points) *L*<sub>1</sub> = 1, *R<sub>k</sub>* + 1 = *L<sub>k+1</sub>* (1 ≤ *k* ≤ *Q* − 1), *R<sub>Q</sub>* = *M*.
*   5.  (24 points) *A<sub>i</sub>* = ⌊(*i*+1)/2⌋, *B<sub>i</sub>* = *i* + 1 (1 ≤ *i* ≤ *N* − 1). Here, ⌊*x*⌋ is the largest integer not exceeding *x*.
*   6.  (41 points) No additional constraints.

## Sample Input and Output

| Sample Input 1 | Sample Output 1 |
| :------------- | :-------------- |
| 7 6 2          | 4               |
| 1 2            | 6               |
| 1 3            |                 |
| 2 4            |                 |
| 2 5            |                 |
| 3 6            |                 |
| 3 7            |                 |
| 2 3 6 4 5 7    |                 |
| 1 3            |                 |
| 4 6            |                 |

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

![](_page_3_Picture_0.jpeg)

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.

![](_page_4_Picture_0.jpeg)

| Sample Input 2  | Sample Output 2 |
| :---------------- | :---------------- |
| 8 8 9             | 3                 |
| 1 2             | 4                 |
| 2 3             | 6                 |
| 3 4             | 6                 |
| 4 5             | 3                 |
| 5 6             | 6                 |
| 6 7             | 1                 |
| 7 8             | 6                 |
| 8 6 4 3 5 2 4 7 | 3                 |
| 3 5             |                   |
| 4 6             |                   |
| 6 8             |                   |
| 1 4             |                   |
| 2 3             |                   |
| 6 8             |                   |
| 5 5             |                   |
| 2 8             |                   |
| 1 2             |                   |

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

![](_page_5_Picture_0.jpeg)

| Sample Input 3  | Sample Output 3 |
| :---------------- | :---------------- |
| 10 7 9            | 1                 |
| 6 5             | 6                 |
| 3 6             | 6                 |
| 9 3             | 4                 |
| 8 3             | 3                 |
| 7 8             | 1                 |
| 7 1             | 7                 |
| 2 5             | 5                 |
| 7 10            | 4                 |
| 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             |                   |

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

Starter code:

Grader code:

Setup script:

Evaluation script: