25398번 - 트리와 집합과 쿼리

문제

N개의 정점으로 이루어진 트리가 있다.

트리의 정점들 위에 돌들을 놓을 수 있는데, 한 정점에는 하나의 돌만 놓을 수 있다.

또한 이 트리는 특이한 성질이 있어서, 두 인접한 정점에 돌을 모두 놓을 수 없다.

트리의 정점들의 부분집합 A 와 B에 대해, A에 포함되는 정점에만 돌이 놓여있는 상태에서 시작하여 하나의 돌을 인접한 정점으로 옮기는 작업만을 반복하여 B에 포함되는 정점에만 돌이 놓여있는 상태를 만들 수 있다면 이 때 f(A,B) = 1, 그렇지 않은 경우 f(A,B) = 0으로 함수 f를 정의하자. 물론, 옮기는 중간 과정에서도 두 인접한 정점에 모두 돌이 있는 경우가 발생해서는 안된다.

당신의 태스크는 여러 집합 쌍에 대해 f에 대한 함수값을 계산하는 것이다.

처음에 두 집합 U, V 는 빈 집합으로 초기화된 상태이며, U, V 에 정점 한 개씩을 추가하는 u v 꼴의 쿼리가 Q개 주어진다.

이는 U에 정점 u를, V에 정점 v를 추가함을 뜻한다.

쿼리가 주어질 때마다 그 쿼리를 처리한 후에 f(U,V)의 값을 계산한 후, 최종적으로 그 Q개의 값들의 합을 출력하시오.

입력

첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T 가 주어지고, 이후 차례로 T 개의 테스트 케이스가 주어진다 (1 ≤ T ≤54).

각 테스트 케이스의 첫 줄에는 트리의 정점 개수를 나타내는 정수 N이 주어진다 (1≤N≤200,000).

이어지는 N-1개의 줄 각각에는 트리의 간선의 양 끝점을 나타내는 두 정수 a와 b가 주어진다 (1≤a≠b≤N).

다음 줄에는 쿼리의 개수를 나타내는 정수 Q가 주어진다 (1≤Q≤N).

이어지는 Q개의 줄 각각에는 순차적으로 집합 U와 V에 추가될 정점을 나타내는 두 정수 u와 v가 주어진다 (1≤u,v≤N).

Q개의 쿼리가 끝난 이후 집합 U 및 집합 V는 인접한 두 정점을 포함하지 않음이 보장된다.

모든 테스트 케이스의 N의 합은 2,000,000을 넘지 않는다.

출력

각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 C는 테스트 케이스의 번호이다.

그 다음 줄에, 계산한 Q개의 f(U,V) 값들의 합을 출력한다.

제한

힌트