트리분할 (KOI 지역예선 2006)

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

1. O(N^3)

dp[node][k][state] 라는 N^2 점화식을 생각해보면 서브 트리에 대해서 http://amugelab.tistory.com/entry/CCC14-Stage-2-Werewolf 의 해법으로 풀 수 있다. 복잡도는 O(N^3).

2. O(N^2)

이 문제에서 두 DP값은 DP[i] = min(DP1[j] + DP2[i-j]) 라는 방식으로 합쳐지는데, 내가 아는 한에서는 이는 O(N^2)보다 빠르게 계산할 수 없다. 아마 실제로도 계산할 수 없을 것이다. 증명은 못하지만...

고로, 뭔가 다른 걸 궁리해야 한다 생각하기 쉬운데 답은 의외로 가까이에 있다. 두 서브트리 사이즈가 A, B이고 여기서 DP배열을 O(AB)에 합칠 수 있는데. 이러한 방식으로 올라가면 T(A+B) = T(A) + T(B) + O(AB) 라는 시간이 걸리고, 이 때 T(N) = O(N^2)이다. 왜냐... 고 물으면, 트리의 각 노드쌍을 본다는 식으로 생각해보자. 노드쌍의 LCA에서는 한번의 merge 연산이 있을 것이지만, 그 외의 경우에는 완전히 다른 서브트리에 있거나 같은 서브트리에 있다. 고로 merge 연산은 각 쌍에 대해서 N^2개 있고 복잡도는 O(N^2)이다. O(AB)에 두 서브트리의 DP값을 합치는 건, 약간 tricky하긴 하지만 절대 힘들지는 않다.

이 문제를 여러개의 색에 대해서 일반화 시킨 문제가 있는데, 조금만 생각해 보면 저 문제 역시 O(N^2)에 풀 수 있다. 고민해보길..

http://www.spoj.com/problems/DRAGON2/