BOJ 28112 - 나무 타기 (Hard)
Sack 을 이용해 $O(N \log ^2N)$ 에 매우 빡빡하게 통과할 수 있다.
좀더 빠른 풀이는 다음과 같다.
트리에서 imos 법을 하자.
DFS를 순회하며 현재 구간합 배열에는 자신의 조상들에 관련된 값만 있게 해보자.
루트의 어떤 DP값을 세는것이 아닌 루트로부터 리프까지 값을 전파해나간다.
$d_i$ 를 노드 $i$의 깊이라고 하고, $b_i$ 를 현재 깊이 $i$ 에 영향을 미치는($d_p+a_p \ge i)$ 조상의 수라고 하자.
DFS를 순회하며 자신이 진입할 때 $b_{d_i+1}$ 에는 $2b_{d_i}$ 를 더해주고, $b_{d_i+1+a_i}$ 에는 $b_{d_i}$ 를 빼준다.
다시 자신이 DFS를 마쳤을 때는 이 값들을 빼서 되돌려놓는다.
이렇게 하면 리프에 도달했을 때 $b_{d_i}$ 값을 전답에 더해주면 된다.
시간복잡도는 $O(N)$ 이다.
Comments