Centroid Decomposition

1. 문제에서 구하고 싶은 구조 (트리에서의 경로 / 트리에서의 연속 컴포넌트)를 루트를 정해놓고, 그 루트를 지나는 것들만 고려했을 때 쉽게 풀 수 있다면 Centroid Decomposition을 이용하여 전체 문제를 해결할 수 있다.

만약 트리에서의 루트가 고정되어 있고, 루트를 지나는 구조들에 대해서는 쉽게 풀 수 있다면, 이제 그 루트를 지나지 않는 경우에 대해서는 Centroid Decomposition의 분할정복 과정에서 다음으로 탐색할 것이다.

이와 같이 생각하면 장점이, 루트를 지나는 경로 / 컴포넌트 등은 각 서브트리에서 문제를 독립적으로 해결할 수 있으니, 가능한 모든 정점쌍 / 집합쌍을 고려하는 대신, 한 서브트리의 정점들을 자료구조 안에 삽입한 후 다른 정점들을 빠르게 찾을 수도 있고, 독립적인 상황으로 만들어 빠르게 전처리한 후 해결할 수 있다.

이 때 주의해야할 점은 루트를 무조건 지나도록 해야하기 때문에, 양쪽 방향으로 스위핑을 하는 등의 작업이 필요할 수도 있다.

이러한 성질 때문에 특히, 트리에서의 거리함수와 관련된 내용이 나왔을 때 쉽게 적용할 수 있다.