Centroid에 관하여

Centroid는 트리의 중심을 의미한다.

 

모든 이웃의 서브트리의 크기가 전체 트리 크기의 절반 이하가 되도록 하는 정점을 의미한다.

 

그렇기 때문에 용도가 재귀적이다.

 

트리에서 $O(N)$이나 $O(NlogN)$ 수준에서 문제의 조건을 만족하는 단 하나의 경로를 찾아야하는 문제에 대해서는 무조건 센트로이드를 떠올려야 한다.

 

 

센트로이드의 정의를 이용한 예제

https://codeforces.com/contest/1205/problem/D

Problem - D - Codeforces

좋은 수학문제다. 센트로이드를 중심으로 이웃 노드를 2개의 파티션으로 분할하여 서브트리의 크기 합이 각각 $N/3$와 $2N/3$ 사이에 오도록 만들 수 있다. 각각의 수를 $a$와 $b$라고 하면, 첫 번째 파티션에는 센트로이드에서 거리가 $1, 2, 3, \dots,  a$ 인 경로가 생기도록 간선에 가중치를 주고. 두 번째 파티션에는 $a+1, 2(a+1), 3(a+1), \dots, b(a+1)$ 까지 만든다. 그러면 센트로이드를 통해 갈 수 있는 거리가 $1$부터 $(a+1)(b+1)-1$ 까지 인 경로들이 모두 존재한다.

 

 

..한 최대 경로 구하기 $O(N^2)$ 미만으로 푸는 예제

모든 경로에 대해 ..한 값을 구하시오. 같은 문제는 어렵다. 모든 경로를 탐색하는데 걸리는 시간이 $O(N^2)$ 이기 때문이다.

 

하지만 센트로이드를 루트로 생각해서, 루트를 중간에 경유하는 경로 중 최대값을 구한다면 꽤 간단해지는 경우가 있다. 이후 센트로이드를 없는 정점으로 간주하고 남은 서브트리들에 관해 작업을 해주면 된다. 시간복잡도가 아래로 볼록한 함수들이라면 젠센 부등식에의해 $O(\log N)$ 정도 오버헤드만 붙어 빠르게 처리된다는 것을 알 수 있다.

 

보통 이런 경우 루트로 올라가는 경로에 대한 정보(ToR), 루트로부터 내려가는 경로에 대한 정보(FromR)을 저장한 후, ToR[x]와 FromR[y] 정보를 혼합하여 정점 x에서 y로 루트를 경유해서 가는 경로를 처리한다.

 

 

https://www.acmicpc.net/problem/15539

15539번: Non-redundant Drive

이제 Well-known이 될만한 유형의 문제이다.

 

센트로이드를 $r$이라고 하자. (루트다.)

정점 $a$에서 $r$로 가는 경로를 $\langle a=a_1, a_2, \dots, a_k = r \rangle$, $r$에서 $b$로 가는 경로를 $\langle r=b_1, b_2, \dots, b_t = b \rangle$ 이라고 하자. $a$에서 $r$로 갈 수 있을 조건은 모든 $i$에 대해 $a_1 - d_{a_1, a_2} + a_2 - d_{a_2, a_3} + \cdots + a_i - d_{a_i, a_{i+1}} \geq 0$ 을 만족하는 것이다. $r$에서 $b$로 가는 경우도 비슷하게 정의된다. To Root에 대한 정보가 주어질 때, 루트에서 남은 연료로 갈 수 있는 최대 높이를 이분탐색으로 찾는다. 각 센트로이드에 대해 $O(N \log N)$이 걸리므로 전체 시간은 $O(N \log^2 N)$ 이다.

 

단순 경로에 대한 부분을 처리하는 부분이 까다롭다. 센트로이드의 이웃 노드를 $s_1, s_2, \dots, s_p$라고 하자. 다음 두 작업을 통해서 이 문제를 해결할 수 있다.

• $i = 1, 2, \dots, p$ 순서대로 루프를 돈다. $s_i$의 서브트리의 모든 노드에서 루트로 가는 경로에 대한 부분을 처리한다. 이후 루트에서 $s_i$의 서브트리의 모든 노드로 가는 경로를 처리한다. 즉 To Root 정보를 먼저, From Root 정보를 나중에 처리한다. 이렇게 루프를 돌면 $x>y$를 만족하는 $s_x$의 서브트리의 임의의 노드에서 $s_y$의 서브트리의 임의의 노드로 가는 단순 경로에 대한 내용이 처리된다.
• $i = p, p-1, \dots, 2, 1$ 순서대로 루프를 돈다. 마찬가지로 $s_i$의 서브트리의 모든 노드에서 루트로 가는 경로에 대한 부분을 처리한다. 이후 루트에서 $s_i$의 서브트리의 모든 노드로 가는 경로를 처리한다. 이렇게 돌면 $x<y$를 만족하는 $s_x$의 서브트리의 임의의 노드에서 $s_y$의 서브트리의 임의의 노드로 가는 단순 경로에 대한 내용이 처리한다.

사실 나는 From Root 정보에서 높이 당 max 값을 2개씩 저장하는 방식으로 처리하긴 했다. 어느 방식이든 좋은 아이디어인 것 같은데, 루프 두 번을 도는 방식이 조금 더 범용적으로 쓰이는 것 같다.

 

 

https://codeforces.com/contest/1303/problem/G

Problem - G - Codeforces

비슷한 문제다. 그런데 센트로이드 최대 경로 + 컨벡스헐 트릭이라는 짬뽕 유형이라 볼 수 있다. 그래도 센트로이드 문제구나! 하는거 빠르게 캐치한 후 성실하게 식 세우고 코드짜면 맞출 수 있는 효자 문제다.

 

Non-redundant Drive 문제와 마찬가지로 $i$를 올라가고 내려가고 하는 루프로 슥슥 갱신해주면 된다. 다만 그 과정에서 컨벡스헐 트릭을 써야하므로 Li Chao 트리를 만들어 From Root에 대한 내용물을 첨가해주면 된다. Li Chao 트리를 초기화할 일이 많은데, 다이나믹 세그먼트 트리를 다 비울 필요 없이 그냥 left, right 자식들을 끊어주기만 하면 된다.

 

캐시 최적화를 안 시켜서 한 13번 정도 TLE를 받았다.. From Root, To Root에 대한 정보를 굳이 배열에 저장하지 않고 DFS를 돌면서 처리하는게 훨씬 random access를 덜 해서 빠르게 돌아가는 것 같다. 한 8배 빠르게 돌아갔다. 큰 교훈을 얻었던 여러모로 좋은 문제이다.

 

 

https://www.acmicpc.net/problem/13854

13854번: 트리와 소수

딱 이 유형 문제. 소수를 미리 에라토스테네스 체로 $p_1, p_2, p_3, \dots$ 다 구해놓는다. 전체 count 변수에 $\sum_i cnt[p_i - d]$를 재귀적으로 더해주면 된다. $N$이 더 크다면 센트로이드+FFT 라는 좀 이상한 문제가 되겠지만.. 다행히 소수의 개수는 얼마 되지 않는다.

 

 

더 찾으면 추가해야지~~