문제 링크
- http://icpc.me/18227
사용 알고리즘
- HLD
- 세그먼트 트리
시간복잡도
- $O(N log^2 N)$
풀이
루트부터 물을 채우기 때문에, 각 정점에서의 정답은 깊이 * 물을 채우는 경로에 속한 횟수가 됩니다.
우리는 루트와 특정 정점을 잇는 경로에 속한 정점에 모두 1씩 더하는 쿼리와, 각 정점의 가중치를 구하는 쿼리를 처리해야 합니다.
이것은 HLD와 세그 레이지(혹은 펜윅)를 이용해 1씩 더하는 쿼리를 $O(log^2 N)$에, 각 정점에 대해 답을 구하는 쿼리를 $O(log N)$에 처리할 수 있습니다.