백준3319 전령들

문제 링크

  • http://icpc.me/3319

문제 출처

  • 2009 CEOI 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)$에 문제를 풀 수 있습니다.