트리 컴포넌트 찾기
시간 제한1초메모리 제한1024 MB
루트가 있는 트리에서 각 질의의 정점 집합을 모두 포함하는 가장 작은 연결 부분 트리의 정점 개수와 번호 합을 구합니다.
문제
정점이 개이고 간선이 개인 트리가 주어진다. 정점 번호는 부터 까지이며, 번 정점이 루트이다. 이 트리에 대해 다음 쿼리를 번 수행한다.
- ... : 정점 를 모두 포함하는 연결 컴포넌트 중 정점 수가 가장 작은 것을 라고 하자. 의 정점 수와 에 속한 정점 번호의 총합을 공백으로 구분하여 출력한다.
입력
첫 번째 줄에 정점의 수 이 주어진다. ()
다음 개 줄에는 부모 정점 번호 와 자식 정점 번호 가 공백으로 구분되어 주어진다. 주어지는 그래프는 트리이다. (, , )
다음 줄에 쿼리의 수 가 주어진다. ()
다음 개 줄에는 가 공백으로 구분되어 주어진다. 모든 의 총합은 이하이다. (, (), ())
입력으로 주어지는 모든 수는 정수이다.
출력
쿼리마다 답을 한 줄에 하나씩 출력한다.