17399번 - 트리의 외심

알고리즘에 푹 빠진 동관이가 트리에 심취한 나머지 트리에서 외심을 정의하려 한다. 트리란, 모든 정점이 연결되어 있으면서 사이클이 존재하지 않는 그래프이다. 하지만 동관이는 트리에서 외심을 정의하기 위해서는 "트리에서 두 정점 사이의 거리"도 정의해야 한다는 사실을 깨달았다!

트리에서 두 정점 사이의 거리는 한 정점에서 다른 정점으로 가기 위해 거쳐야 하는 최소한의 간선의 개수로 정의된다. 이 때 트리의 세 정점에 대해, 트리의 외심은 세 정점으로부터 거리가 같으면서, 그 거리를 최소로 하는 정점이 존재한다면 해당 정점으로 정의된다. 수학적으로 트리의 세 정점에 대해 외심이 존재한다면, 유일하다는 것을 보일 수 있다.

자명하게도, 외심을 정의하는 3개의 정점이 달라지면 같은 트리라 해도 외심이 달라진다. 동관이는 다양한 외심들을 찾아보고 싶지만 코딩에 귀찮음을 겪고 있다......동관이를 위해 여러분들이 대신 코드를 짜주도록 하자.

첫 번째 줄에 정점의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 이 트리는 1번 정점, 2번 정점, ..., N번 정점으로 구성된다.

두 번째 줄부터 N번째 줄까지, 트리의 간선 정보를 의미하는 두 자연수 X, Y가 공백으로 구분되어 주어진다. 이는 X번 정점과 Y번 정점이 연결되어있음을 의미한다. (1 ≤ X, Y ≤ N, X ≠ Y)

주어지는 연결관계는 트리를 구성한다.

N+1 번째 줄에는 쿼리의 개수 Q가 주어진다. (1 ≤ Q ≤ 100,000)

다음 Q개의 줄에 걸쳐, 외심을 정의하기 위한 세 개의 정점 번호를 뜻하는 세 자연수 A, B, C가 공백으로 구분되어 주어진다. (1 ≤ A, B, C ≤ N) 

Q개의 줄에 걸쳐 각 쿼리마다 입력으로 주어진 세 정점에 대해 트리의 외심이 존재하면 외심의 정점 번호를, 존재하지 않으면 -1을 출력한다.