만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

관광

시간 제한4초메모리 제한1024 MB

요약
섬들이 나무 구조로 이어진 지도에서 L번부터 R번까지 관광지가 있는 섬을 모두 잇는 최소 섬 개수를 구합니다.
난이도

어려움10점 중 8점

유형
트리, 슬라이딩 윈도우, 정렬
정답자
아직 제출이 없습니다

문제

JOI 왕국은 NN개의 섬으로 이루어진 섬나라입니다. 섬에는 1번부터 NN번까지 번호가 매겨져 있습니다. 섬들은 N−1N - 1개의 다리로 연결되어 있으며, 다리에는 1번부터 N−1N - 1번까지 번호가 매겨져 있습니다. 다리 ii (1≤i≤N−11 \le i \le N - 1)는 섬 AiA_i와 섬 BiB_i를 양방향으로 잇습니다. 다리를 건너면 어느 섬에서든 다른 모든 섬으로 갈 수 있습니다.

관광지는 MM곳이 있으며, 1번부터 MM번까지 번호가 매겨져 있습니다. 관광지 jj (1≤j≤M1 \le j \le M)는 섬 CjC_j에 있습니다.

여행자는 QQ명이며, 1번부터 QQ번까지 번호가 매겨져 있습니다. 여행자 kk (1≤k≤Q1 \le k \le Q)는 관광지 Lk,Lk+1,…,RkL_k, L_{k+1}, \dots, R_k를 모두 방문하려고 합니다. 여행자의 여정은 다음과 같습니다.

  1. 여행자는 섬 xx (1≤x≤N1 \le x \le N)를 고르고, 비행기를 타고 그 섬에 도착합니다.
  2. 여행자는 다음 행동을 순서와 종류에 제약 없이 원하는 만큼 반복합니다.
    • 현재 섬의 관광지를 골라 방문한다.
    • 다리를 건너 다른 섬으로 이동한다.
  3. 여행자는 비행기를 타고 JOI 왕국을 떠납니다.

예산이 제한되어 있어서, 여행자 kk는 적어도 한 번 방문하는 섬의 수를 최소로 줄이려고 합니다. 각 kk에 대해 그 최솟값을 구하세요.

입력

입력은 다음 형식으로 주어집니다.

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

출력

QQ개의 줄을 출력합니다. kk번째 줄에는 여행자 kk가 적어도 한 번 방문하는 섬 수의 최솟값을 출력합니다.

제한

  • 1≤N≤100 0001 \le N \le 100\,000
  • 1≤M≤100 0001 \le M \le 100\,000
  • 1≤Q≤100 0001 \le Q \le 100\,000
  • 1≤Ai≤N1 \le A_i \le N (1≤i≤N−11 \le i \le N - 1)
  • 1≤Bi≤N1 \le B_i \le N (1≤i≤N−11 \le i \le N - 1)
  • 다리를 건너서 어느 섬에서든 다른 모든 섬으로 갈 수 있습니다.
  • 1≤Cj≤N1 \le C_j \le N (1≤j≤M1 \le j \le M)
  • 1≤Lk≤Rk≤M1 \le L_k \le R_k \le M (1≤k≤Q1 \le k \le Q)
  • 주어지는 모든 값은 정수입니다.

예제3

  1. 예제 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
    예상 출력
    4
6

  2. 예제 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
    예상 출력
    3
4
6
6
3
6
1
6
3

  3. 예제 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