28000번 - Tourism 서브태스크다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 1024 MB112373333.333%

문제

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}, \dots , 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$ $\cdots$ $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.

제한

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

서브태스크

번호배점제한
15

$N ≤ 300$, $M ≤ 300$, $Q ≤ 300$.

25

$N ≤ 2\,000$, $M ≤ 2\,000$, $Q ≤ 2\,000$.

37

$A_i = i$, $B_i = i + 1$ ($1 ≤ i ≤ N - 1$).

418

$L_1 = 1$, $R_k + 1 = L_{k+1}$ ($1 ≤ k ≤ Q - 1$), $R_Q = M$.

524

$A_i = \left\lfloor \frac{i+1}{2} \right\rfloor$, $B_i = i + 1$ ($1 ≤ i ≤ N - 1$). Here, $\left\lfloor x \right\rfloor$ is the largest integer not exceeding $x$.

641

No additional constraints.

예제 입력 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

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.

예제 입력 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

This sample input satisfies the constraints of Subtasks 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

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

출처

Camp > JOI Spring Training Camp > JOI 2022/2023 Spring Training Camp 3-3번

채점 및 기타 정보

  • 예제는 채점하지 않는다.

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)