문제 링크
- http://icpc.me/16002
사용 알고리즘
- CHT
시간복잡도
- $O(N log^2 N)$
풀이
Union을 했는데 더 시끄러워지는 경우는 없습니다. Union은 할 수 있으면 해주는 것이 이득이고, 결국 마지막에는 모든 도로의 끝점이 리프 노드인 포레스트가 나올 것입니다.
루트가 아닌 어떤 정점 v의 서브트리를 생각해봅시다. v의 조상 중 하나는 최종 결과에서 v의 서브트리 안에 있는 리프 노드와 연결이 될 것입니다. 그리고 나머지 리프 노드는 v의 서브트리 내부에서 어떻게 잘 해결되겠죠. 트리 DP를 생각해볼 수 있습니다.
D(v, l) = v의 조상 중 하나가 v의 서브트리 내부에 있는 리프 노드 l과 연결되었을 때, v의 서브트리에서 만들어지는 최솟값 상태 전이는 아래처럼 할 수 있습니다.
- v == l인 경우 : 0
- v != l인 경우 : D(u, l) + $\sum_{w ≠ v ∧ w ∈ child(v)} min(D(w, l’) + A_v A_{l’})$
$D(w, l’) + A_v A_{l’}$가 최소가 되는 $l’$를 전처리하면 $O(N^2)$에 DP Table을 채울 수 있습니다. 최적화를 해봅시다.
v의 서브트리에 있는 모든 리프 노드 l에 대해 직선 $f_l(x) = A_l \times x + D(v, l)$을 그려주면 CHT를 사용할 수 있는 꼴이 만들어집니다.
v의 자식 u에 대해 $min(D(u, l’) + A_v A_{l’})$은 u의 서브트리로 만든 CHT에서 $x = A_v$의 값을 가져오는 것으로 쉽게 구할 수 있습니다.
v의 자식 u에 대해 v의 조상과 u의 서브트리에 속한 리프 노드가 연결된다면, u의 서브트리로 만든 CHT의 직선들이 $\sum_{w ≠ v ∧ w ∈ child(v)} min(D(w, l’) + A_v A_{l’})$만큰 위로 올라가게 됩니다.
즉, 우리는
- CHT에서 특정 X 좌표에 대해 답을 구하는 것
- CHT에 있는 직선들을 y축 방향으로 평행이동하는 것
- 두 개의 CHT를 합치는 것
을 잘 해주면 DP값을 구할 수 있습니다.
1번은 쉽게 할 수 있고, 2번은 up[v] = v의 서브트리로 만든 CHT가 y축 방향으로 이동한 양 배열을 관리해주면 처리할 수 있습니다.
3번은 직선의 개수가 적은 CHT의 직선을 직선이 많은 CHT에 넣어주는 것으로(small to large) 수행할 수 있습니다.
1번 연산은 총 N번 수행하므로 $O(N log N)$이 걸리고, 3번 연산은 small to large에 의해 $O(N log^2 N)$이 걸립니다.
$O(N log^2 N)$에 문제를 풀 수 있게 됩니다.