Security Vulnerability Patch

트리를 DFS 전위 순회 순서로 $a_1,a_2,\ldots,a_N$이라 하자. $a_1=1$이다. 전위 순회에서는 모든 정점의 서브트리가 하나의 연속 구간을 이룬다.

$a_i$의 서브트리 크기를 $s_{a_i}$라 하고, 그 서브트리 바로 다음 위치를

$$R_i=i+s_{a_i}$$

라 하자. $R_i=N+1$일 수도 있다.

어떤 정점에 --force 수정을 수행했다면 그 정점의 서브트리 안에서는 다른 작업을 추가로 수행할 필요가 없다. 그 안의 작업을 모두 제거해도 취약점은 그대로 해결되어 있고, 비용과 --force 사용 횟수는 증가하지 않는다.

$D_t[i]$를 전위 순회에서 $a_i,a_{i+1},\ldots,a_N$만 남았을 때, 수정을 최대 번 사용하여 모든 취약점을 해결하는 최소 비용이라 하자.

$t=0$이면 일반 수정만 사용할 수 있으므로

$$D_0[i]=C_{a_i}+D_0[i+1]$$

이다.

$t\ge 1$일 때 $a_i$에서 가능한 선택은 두 가지이다.

• $a_i$에 --force를 사용하지 않는다. 비용은 $C_{a_i}+D_t[i+1]$이다.

따라서

$$D_t[i]=\min\left(C_{a_i}+D_t[i+1],\ F_{a_i}+D_{t-1}[R_i]\right)$$

이다.

항상 $R_i>i$이므로 각 $t$에 대해 $i=N,N-1,\ldots,2$ 순서로 계산할 수 있다. 번 정점은 작업 대상이 아니므로 정답은 이다.

현재 $D_t$를 계산할 때 필요한 것은 같은 층의 $D_t[i+1]$과 직전 층의 $D_{t-1}$뿐이다. 따라서 두 개의 길이 배열만 유지하면 된다.

전위 순회와 서브트리 크기를 구하는 데 $O(N)$, DP에 $O(N(K+1))$ 시간이 걸린다. 공간 복잡도는 $O(N)$이다.

Solution written by GPT5.6