I - 旅行 (Tourism) 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MiB

Score: 100 points

Problem Statement

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 \le i \le 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 \le j \le 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 \le x \le 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 \le k \le Q) wants to visit all of the sightseeing spots L_k, L_k + 1, \ldots, 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 \le k \le Q), the minimum possible number of islands where the traveler k visits at least once.


Input

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 \cdots C_M
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

Output

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

Constraints

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

Subtasks

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

Sample Input 1

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

Sample Output 1

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 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.


Sample Input 2

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

Sample Output 2

3
4
6
6
3
6
1
6
3

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


Sample Input 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

Sample Output 3

1
6
6
4
3
1
7
5
4

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

配点 : 100 点

問題文

JOI 国は N 個の島からなる島国であり,島には 1 から N までの番号が付けられている.これらの島は N - 1 本の橋で結ばれており,橋には 1 から N - 1 までの番号が付けられている.橋 i (1 \leqq i \leqq N - 1) は島 A_i と島 B_i を双方向に結んでいる.どの島からどの島へも何本かの橋を渡ることで移動できる.

JOI 国には M 個の観光地があり,1 から M までの番号が付けられている.観光地 j (1 \leqq j \leqq M) は島 C_j にある.

Q 人の旅行者が JOI 国の観光地を見物しようとしている.旅行者には 1 から Q までの番号が付けられている.それぞれの旅行者は以下のように旅行をする.

  1. ある島 x (1 \leqq x \leqq N) を選び,飛行機で島 x に到着する.
  2. 以下の 2 種類の行動を自由な順序で何回か繰り返す.
    • 現在いる島にある観光地を 1 つ選び,その観光地を見物する.
    • 橋を渡り,別の島へ移動する.
  3. 現在いる島から飛行機で出国する.

旅行者 k (1 \leqq k \leqq Q) は観光地 L_k, L_k + 1, \ldots, R_k をすべて見物したいが,予算の都合上,1 回以上訪れる島の個数がなるべく少なくなるようにしたい.

JOI 国の情報と旅行者の情報が与えられたとき,それぞれの k (1 \leqq k \leqq Q) について,旅行者 k が 1 回以上訪れる島の個数としてありうる最小値を求めるプログラムを作成せよ.


入力

入力は以下の形式で標準入力から与えられる.

N M Q
A_1 B_1
A_2 B_2
\vdots
A_{N - 1} B_{N - 1}
C_1 C_2 \cdots C_M
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

出力

標準出力に Q 行出力せよ.k 行目 (1 \leqq k \leqq Q) には,旅行者 k が 1 回以上訪れる島の個数としてありうる最小値を出力せよ.

制約

  • 1 \leqq N \leqq 100\,000.
  • 1 \leqq M \leqq 100\,000.
  • 1 \leqq Q \leqq 100\,000.
  • 1 \leqq A_i \leqq N (1 \leqq i \leqq N - 1).
  • 1 \leqq B_i \leqq N (1 \leqq i \leqq N - 1).
  • どの島からどの島へも何本かの橋を渡ることによって移動することができる.
  • 1 \leqq C_j \leqq N (1 \leqq j \leqq M).
  • 1 \leqq L_k \leqq R_k \leqq M (1 \leqq k \leqq Q).
  • 入力される値はすべて整数である.

小課題

  1. (5 点) N \leqq 300,M \leqq 300,Q \leqq 300.
  2. (5 点) N \leqq 2\,000,M \leqq 2\,000,Q \leqq 2\,000.
  3. (7 点) A_i = i,B_i = i + 1 (1 \leqq i \leqq N - 1).
  4. (18 点) L_1 = 1,R_k + 1 = L_{k+1} (1 \leqq k \leqq Q - 1),R_Q = M.
  5. (24 点) A_i = \left\lfloor \frac{i+1}{2} \right\rfloor,B_i = i + 1 (1 \leqq i \leqq N - 1).ただし,\lfloor x \rfloor は x を超えない最大の整数を表す.
  6. (41 点) 追加の制約はない.

入力例 1

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

出力例 1

4
6

旅行者 1 は以下のように旅行をして観光地 1, 2, 3 をすべて見物することができる.

  1. 島 2 に到着する.
  2. 島 2 にある観光地 1 を見物する.
  3. 橋 1 を渡り,島 2 から島 1 へ移動する.
  4. 橋 2 を渡り,島 1 から島 3 へ移動する.
  5. 島 3 にある観光地 2 を見物する.
  6. 橋 5 を渡り,島 3 から島 6 へ移動する.
  7. 島 6 にある観光地 3 を見物する.
  8. 島 6 から出国する.

このとき,旅行者 1 が 1 回以上訪れた島は島 1, 2, 3, 6 の 4 個となる.1 回以上訪れる島の個数が 3 個以下になるように観光地 1, 2, 3 をすべて見物することはできないので,1 行目には 4 を出力する.

旅行者 2 は以下のように旅行をして観光地 4, 5, 6 をすべて見物することができる.

  1. 島 3 に到着する.
  2. 橋 6 を渡り,島 3 から島 7 へ移動する.
  3. 島 7 にある観光地 6 を見物する.
  4. 橋 6 を渡り,島 7 から島 3 へ移動する.
  5. 橋 2 を渡り,島 3 から島 1 へ移動する.
  6. 橋 1 を渡り,島 1 から島 2 へ移動する.
  7. 橋 3 を渡り,島 2 から島 4 へ移動する.
  8. 島 4 にある観光地 4 を見物する.
  9. 橋 3 を渡り,島 4 から島 2 へ移動する.
  10. 橋 4 を渡り,島 2 から島 5 へ移動する.
  11. 島 5 にある観光地 5 を見物する.
  12. 島 5 から出国する.

このとき,旅行者 2 が 1 回以上訪れた島は島 1, 2, 3, 4, 5, 7 の 6 個となる.1 回以上訪れる島の個数が 5 個以下になるように観光地 4, 5, 6 をすべて見物することはできないので,2 行目には 6 を出力する.

この入力例は小課題 1, 2, 4, 5, 6 の制約を満たす.


入力例 2

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

出力例 2

3
4
6
6
3
6
1
6
3

この入力例は小課題 1, 2, 3, 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

出力例 3

1
6
6
4
3
1
7
5
4

この入力例は小課題 1, 2, 6 の制約を満たす.


出典

JOI 2022/2023 春季トレーニング Contest Day3 問題3