[BOJ] 15480번: LCA와 쿼리

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

일단 아무거나 루트로 두고 LCA를 구하기 위한 sparse table을 만들어놓고 나면 r, u, v에 대한 정답은 (r과 u의 lca), (r과 v의 lca), (u와 v의 lca)중 depth가 가장 큰 것입니다. u,v가 r의 자손일 때, 둘 다 아닐 때, 하나만 자손이고 하나는 아닐 때 등으로 케이스를 나눠서 생각해보면 이 알고리즘이 성립함을 알 수 있습니다.

https://github.com/blisstoner/BOJ/blob/master/15480.cpp