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

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

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

그런데 트리 T의 어떤 정점들에는 검은 돌이 놓여있다.

검은 돌은 한 정점에 많아야 하나씩만 놓일 수 있다.

우리는 다음과 같은 질의 q = ( i, j )를 던질 것이고 여러분들은 이 질의에 답해야한다:

예를 들어서, 아래 <그림 1>에서 9개 정점을 가진 트리가 주어진다.

여기서 질의 q = ( 5, 3 )에 대해서 위의 조건을 만족하는 정점 1, 2, 3, 4, 6으로 이루어진 서브트리가 존재한다.

하지만 질의 q₂ = ( 4, 3 )에 대해서는 조건을 만족하는 서브트리는 존재하지 않는다.

N개의 정점을 가진 트리와 Q개의 질의 q가 주어질 때, 각각의 질의에 대한 답 중에서 ‘존재한다’는 답의 총 개수를 출력하시오.

검은 돌(stones) timer 6s memory 512MB

검은 돌(stones) 6s 512MB