BOJ 17399 트리의 외심

https://www.acmicpc.net/problem/17399

17399번: 트리의 외심

일단 각 쿼리에 대해 트리에서 최소 공통 조상(Lowest Common Ancestor)을 log n에 구할 수 있어야 한다.

알고리즘

1. 두 정점 a와 b에 대해, 두 정점의 가운데에 위치한 정점 x를 찾는다.
   1. a와 b 거리가 짝수여야 한다. 그렇지 않으면 가운데에 위치한 정점을 정의할 수 없다.
2. 단계 1에서 찾은 정점 x로부터 정점 c까지의 거리를 구한다.
3. x로부터 각 정점 a, b, c까지의 거리가 같으면 x가 트리의 외심이다.
4. 주어진 세 정점 q, p, r에 대해서 위 1~3 단계를 돌아가면서 시도해 본다. ((a=q, b=p, c=r), (p, r, q), (r, q, p)) 만약 외심 x를 찾을 수 있는 경우가 있으면, 그 x가 세 정점에 대한 외심이다.

두 정점의 거리를 구하기

1. 두 정점 a, b의 최소 공통 조상 p를 찾는다. (log n)
   • a == p 인 경우, dist(a, b) = depth(b) - depth(a)
   • b == p 인 경우, dist(a, b) = depth(a) - depth(b)
   • else,  dist(a, b) = depth(a) - depth(p) + depth(b) - depth(p) = depth(a) + depth(b) - 2 * depth(p)

두 정점의 가운데에 위치한 정점 x 찾기

1. 두 정점의 a, b의 거리 d를 구한다. (log n)
2. 정점 a와 b중 depth가 더 깊은 정점으로부터 d/2만큼 올라간 정점을 찾는다. (log n)