검은 돌(stones) > 문제은행



문제은행

3436 : 검은 돌(stones)

제한시간: 2Sec    메모리제한: 512mb
해결횟수: 2회    시도횟수: 8회   



정점들의 집합  V(≠∅)와 간선들의 집합 를 가진 그래프 T = ( V, E )가 트리라 함은

T​ 의 임의의 두 정점 uv사이에 항상 경로가 존재하고 그 경로는 하나뿐인 경우이다.

 

트리 T = ( V, E )​안의 서브트리 S = (V , E) 란, V​ ⊆ V, E​ ⊆ E 이면서 위의 트리의 성
질을 만족하는 그 자체로 트리인 그래프이다.

그런데 트리 T​의 어떤 정점들에는 검은 돌이 놓여있다.
검은 돌은 한 정점에 많아야 하나씩만 놓일 수 있다.

우리는 다음과 같은 질의 q = ( i, j )를 던질 것이고 여러분들은 이 질의에 답해야한다:
  • 트리 T​ 안에 정확히 개의 정점을 가지고 이중에 개의 정점에 검은 돌이
    놓여 있는 서브트리  S가 존재하는가?
예를 들어서, 아래 <그림 1>에서 9개 정점을 가진 트리가 주어진다. 
여기서 질의 q = ( 5, 3 )​에 대해서 위의 조건을 만족하는 정점 1, 2, 3, 4, 6으로 이루어진 서브트리가 존재한다. 
하지만 질의 q2 = ( 4, 3 )​에 대해서는 조건을 만족하는 서브트리는 존재하지 않는다.

592d7a7e0c8d86d1da5cb1fdc052ff77_1563697
N개의 정점을 가진 트리와 Q​개의 질의 q​가 주어질 때, 

각각의 질의에 대한 답 중에서 ‘존재한다’는 답의 총 개수를 출력하시오.​

 

 


표준 입력으로 다음 정보가 주어진다. 
입력의 첫 줄에는 트리 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점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다


표준 출력으로 각각의 질의에 대한 답 중에서 ‘존재한다’는 답의 총 개수를 출력한다.

[Copy]
3 0

1 2
2 3
4
1 0
2 0
1 0
3 0
[Copy]
4


[Copy]
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
[Copy]
1






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.