3436 : 검은 돌(stones)
- 제한시간
- 6000 ms
- 메모리제한
- 512 MB
- 해결횟수
- 6 회
- 시도횟수
- 94 회
문제
정점들의 집합 V(≠∅)와 간선들의 집합 E 를 가진 그래프 T = ( V, E )가 트리라 함은
T 의 임의의 두 정점 u 와 v사이에 항상 경로가 존재하고 그 경로는 하나뿐인 경우이다.
- 트리 T 안에 정확히 i 개의 정점을 가지고 이중에 j 개의 정점에 검은 돌이 놓여 있는 서브트리 S가 존재하는가?

입력형식
표준 입력으로 다음 정보가 주어진다.
입력의 첫 줄에는 트리 T의 정점의 개수를 나타내는 정수 N ( 1 ≤ N ≤ 5,000) 과
정점들에 놓여있는 검은 돌의 개수 B ( 1 ≤ B ≤ N) 가 주어진다.
여기서, 트리 T의 정점은 1부터 N까지 정수로 나타낸다.
두 번째 줄에는 검은 돌이 놓여 있는 정점을 나타내는 B개의 정수 x(1 ≤ x ≤ N)가 주어진다.
이어지는 N-1 개 줄 각각에 T에서 간선이 존재하는 두 정점을 나타내는 정수 u, v(1 ≤ u, v ≤ N)가 주어진다.
다음 줄에는 질의의 개수 Q(1 ≤ Q ≤ 1,000,000)가 주어지고,
이어지는 Q개의 줄 각각에 하나의 질의 q = (i, j) 를 나타내는 두 정수 i, j(1 ≤ i ≤ N, 0 ≤ j ≤ min(i, B))가 주어진다.
[부분문제의 제약 조건]
* 부분문제 1: 전체 점수 100점 중 9점에 해당하며 N ≤ 15, Q ≤ 200다.
* 부분문제 2: 전체 점수 100점 중 27점에 해당하며 N ≤ 100, Q ≤ 10,000이다.
* 부분문제 3: 전체 점수 100점 중 28점에 해당하며 N ≤ 5,000, B ≤ 100, Q ≤ 1,000,000이다.
* 부분문제 4: 전체 점수 100점 중 36점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다.
출력형식
입력 예3 0 1 2 2 3 4 1 0 2 0 1 0 3 0 |
출력 예4 |
입력 예9 4 1 9 6 4 1 2 2 4 2 3 4 5 3 6 6 7 6 8 8 9 2 5 3 4 3 |
출력 예1 |