onjo0127의 블로그

문제 Sparse Table을 통해 문제를 해결할 수 있다. $par_{i, k}$를 $i$번 정점에서 $2^k$번 위로 올라간 정점이라고 정의하면, $par_{i, k} = par_{par_{i, k-1}, k-1}$과 같은 점화식으로 par를 채울 수 있다. 이걸 Sparse Table이라고 하나보다. par 배열을 통해 임의의 정점에서 $K$번 위로 올라간 정점을 $O(logK)$만에 찾을 수 있다. $dist_i$를 루트에서 $i$번 정점까지의 거리라고 정의하면 1번 쿼리의 답은 $dist_u+dist_v-2*dist_{lca(u,v)}$이다. 2번 쿼리는 $K$번째 정점이 어디에 위치하는가만 알면 Sparse Table로 $K$번째 정점을 찾을 수 있다. $K$번째 정점이 $u$와 $LCA(u,..