Security Vulnerability Patch

List the vertices in DFS preorder as $a_1,a_2,\ldots,a_N$, where $a_1=1$. In preorder, the subtree of every vertex forms one contiguous interval.

Let $s_{a_i}$ be the size of the subtree rooted at $a_i$, and define the position immediately after that subtree as

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

It is possible that $R_i=N+1$.

If a --force patch is applied to a vertex, no additional operation inside its subtree is necessary. Removing all such redundant operations keeps every vulnerability fixed and never increases the cost or the number of --force patches.

Let $D_t[i]$ be the minimum cost to fix all vulnerabilities among $a_i,a_{i+1},\ldots,a_N$ using at most patches.

When $t=0$, only normal patches may be used, so

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

For $t\ge 1$, there are two choices at $a_i$.

• Do not use --force at $a_i$. The cost is $C_{a_i}+D_t[i+1]$.

Therefore,

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

Since $R_i>i$, for each $t$ the states can be evaluated in the order $i=N,N-1,\ldots,2$. Vertex cannot be patched, so the answer is .

To compute the current layer $D_t$, we only need $D_t[i+1]$ from the same layer and $D_t$ from the previous layer. Thus only two arrays of length are needed.

The preorder and subtree sizes take $O(N)$ time. The DP takes $O(N(K+1))$ time and $O(N)$ memory.

Solution written by GPT5.6