시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 2502 | 1165 | 853 | 45.664% |
N개의 정점으로 이루어져 있는 트리 T가 주어졌을 때, 다음 쿼리를 수행하는 프로그램을 작성하시오.
r u v
: T의 루트가 r이라고 했을 때, u와 v의 LCA를 출력한다.첫째 줄에 정점의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리 T의 간선 정보 u와 v가 주어지다. u와 v는 트리의 간선을 나타내는 두 정점이다.
다음 줄에는 쿼리의 개수 M(1 ≤ M ≤ 100,000)가 주어진다. 다음 M개의 줄에는 쿼리를 나타내는 r, u, v가 주어진다.
각각의 쿼리마다 한 줄에 하나씩 결과를 출력한다.
7 1 2 2 3 2 4 1 5 5 6 4 7 5 1 2 7 3 1 5 2 1 7 5 6 2 6 2 3
2 1 2 5 2