BOJ 12023 - 연세대학교 포인트 게임
Centroid Decomposition문제인데, 개인적으로 트리와 쿼리 5보다 고려할게 있다고 생각한다.
일단 LCA 를 활용하여 두 정점간의 거리를 $O(\log n)$에 구할 수 있게 전처리한다.
$1$번 쿼리는 정점이 $u$ 라면 센트로이드 트리에서 자신의 부모들에 연속적으로 $d(u, p)$ 를 갱신한다.
파란곳이 한 번 더 칠해지는 경우 무시해야한다.
$2$번 쿼리는 좀더 신경써야 한다.
그냥 센트로이드 트리에서 $p'$ 들의 $\sum d$ 를 더하는 건 중복된 파랑색들이 더해지기 때문이다.
따라서 $c(p, child)$ 를 부모 $p$ 에서 자식 $child$ 에서 오는 파랑색까지의 경로의 합이라고 두고,
그만큼은 더해주지 않고 진행해야한다.
Comments