국제 옥토끼 기구 (BOJ 17348) https://www.acmicpc.net/problem/17348 Centroid decomposition을 이용한다.각 센트로이드 $C$에 대해서 $C$가 담당하는 부분 트리의 각 정점 $V$에 대해 $distance(C, V)$를 모아서 정점 번호 기준으로 세그먼트 트리를 만들 수 있다.쿼리로 받은 정점 $V$에서 부모 센트로이드로 올라가면서 아직 처리되지 않은 정점들 중에 $[L, R]$ 구간에 속하는 정점의 값을 계속해서 더해주어 답을 구할 수 있다. 이 때 현재 처리된 정점들은 현재 센트로이드를 기준으로 했을 때 $V$가 속하는 서브트리의 정점들이고, 이 서브트리들의 정점을 제외하고 계산할 수 있는 세그먼트 트리를 만들면 된다. 쿼리의 답을 구하는 과정을 아래의 pseudo-code와 같이 구.. 더보기 이전 1 2 3 4 5 6 ··· 24 다음