DOJ logoDOJ
Problems
Recently added problemsSaved problemsWorkbooks
CategoriesDLCContestsGroupsTeamsBoard
Ranking
Solved Problem RankingStreak rankingDOJ Power ranking
Status
Call for TasksLoginRegister
DOJ logoDOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord account linking.

Problems
ProblemsCategories
Community
ContestsRankingBoardNoticesHost an external contestGuide
Account
LoginRegisterJudge Status
Policy
Terms of ServiceDLC RulesPrivacyAPI documentationLanguage runtimesContest rank rewardsRating and performance
© 2026 DOJ
All rights reserved
Editorial

Security Vulnerability Patch

Back to problem

Editorial

List the vertices in DFS preorder as a1,a2,…,aNa_1,a_2,\ldots,a_Na1​,a2​,…,aN​, where a1=1a_1=1a1​=1. In preorder, the subtree of every vertex forms one contiguous interval.

Let sais_{a_i}sai​​ be the size of the subtree rooted at aia_iai​, and define the position immediately after that subtree as

Ri=i+sai.R_i=i+s_{a_i}.Ri​=i+sai​​

It is possible that Ri=N+1R_i=N+1Ri​=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 Dt[i]D_t[i]Dt​[i] be the minimum cost to fix all vulnerabilities among ai,ai+1,…,aNa_i,a_{i+1},\ldots,a_Nai​,a using at most patches.

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

D0[i]=Cai+D0[i+1].D_0[i]=C_{a_i}+D_0[i+1].D0​[i]=Cai​

For t≥1t\ge 1t≥1, there are two choices at aia_iai​.

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

Therefore,

Dt[i]=min⁡(Cai+Dt[i+1], Fai+Dt−1[Ri]).D_t[i]=\min\left(C_{a_i}+D_t[i+1],\ F_{a_i}+D_{t-1}[R_i]\right).Dt​[i]=min(C

Since Ri>iR_i>iRi​>i, for each ttt the states can be evaluated in the order i=N,N−1,…,2i=N,N-1,\ldots,2i=N,N. Vertex cannot be patched, so the answer is .

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

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

Solution written by GPT5.6

.
i+1
​
,
…
,
aN​
ttt
--force
​
+
D0​[i+
1].
+
Dt​[i+
1]
  • Use --force at aia_iai​. Its whole subtree is fixed, so the cost is Fai+Dt−1[Ri]F_{a_i}+D_{t-1}[R_i]Fai​​+Dt−1​[Ri​].
  • ai​
    ​
    +
    Dt​
    [
    i
    +
    1
    ]
    ,
     
    Fai​​
    +
    Dt−1​
    [
    Ri​
    ]
    )
    .
    −
    1,…,2
    111
    DK[2]D_K[2]DK​[2]
    −1[Ri]D_{t-1}[R_i]
    Dt−1​[Ri​]
    O(N)O(N)O(N)