문제 링크
- http://icpc.me/3319
문제 출처
- 2009 CEOI Day1 2번
사용 알고리즘
- CHT
시간복잡도
- $O(N log N)$
풀이
N 제한이 작은 경우에는 v의 모든 조상 i에 대해 $D(v) = min(D(i) + (dep(v) - dep(i)) \times V_v) + S_v$를 계산해주면 $O(N^2)$에 풀 수 있습니다.
점화식을 보면 CHT의 느낌을 강하게 받을 수 있습니다. N ≤ 1e5이기 때문에 $O(N log N)$ 정도에 CHT를 해주면 문제를 풀 수 있을 것 같다는 생각이 납니다. 하지만 배열이 아닌 트리에서 해야하는 것이 문제입니다.
일단 CHT는 리차오 트리로 편하게 할 수 있습니다. 리차오 트리에 직선을 삽입할 때 값이 변하는 정점들을 스택에 넣어두고, roll back할 때 스택에서 빼주는 방식으로 구현해주면 됩니다. 직선 삽입, 최솟값 구하기, roll back을 각각 $O(log N)$에 할 수 있으므로 $O(N log N)$에 문제를 풀 수 있습니다.