BOJ 12023 - 연세대학교 포인트 게임

May 28, 2023

Centroid Decomposition문제인데, 개인적으로 트리와 쿼리 5보다 고려할게 있다고 생각한다.

일단 LCA 를 활용하여 두 정점간의 거리를 $O(\log n)$ 에 구할 수 있게 전처리한다.

$1$ 번 쿼리는 정점이 $u$ 라면 센트로이드 트리에서 자신의 부모들에 연속적으로 $d(u, p)$ 를 갱신한다.

파란곳이 한 번 더 칠해지는 경우 무시해야한다.

$2$ 번 쿼리는 좀더 신경써야 한다.

그냥 센트로이드 트리에서 $p'$ 들의 $\sum d$ 를 더하는 건 중복된 파랑색들이 더해지기 때문이다.

따라서 $c(p, child)$ 를 부모 $p$ 에서 자식 $child$ 에서 오는 파랑색까지의 경로의 합이라고 두고,

그만큼은 더해주지 않고 진행해야한다.

You may also enjoy