DOJ logoDOJ
题目
最近添加的题目收藏的题目Workbooks
分类DLC比赛小组团队讨论区
排名
解题数量排行榜连续解题排名DOJ Power 排行榜
评测状态
征题登录注册
DOJ logoDOJ

支持 OI 子任务计分、Elo 等级分和 Discord 账号绑定的社区在线评测系统。

题目
题目列表分类
社区
比赛排名讨论区公告举办外部比赛指南
账号
登录注册评测状态
政策
服务条款DLC 使用规则隐私政策API 文档语言运行环境比赛排名奖励评级与表现
© 2026 DOJ
保留所有权利
题解

Security Vulnerability Patch

返回题目

题解

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

aia_iai​의 서브트리 크기를 sais_{a_i}sai​​라 하고, 그 서브트리 바로 다음 위치를

Ri=i+saiR_i=i+s_{a_i}Ri​=i+sai​​

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

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

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

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

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

이다.

t≥1t\ge 1t≥1일 때 aia_iai​에서 가능한 선택은 두 가지이다.

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

따라서

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

이다.

항상 Ri>iR_i>iRi​>i이므로 각 ttt에 대해 i=N,N−1,…,2i=N,N-1,\ldots,2i=N,N 순서로 계산할 수 있다. 번 정점은 작업 대상이 아니므로 정답은 이다.

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

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

Solution written by GPT5.6

i+1
​
,
…
,
aN​
--force
ttt
+
D0​[i+
1]
+
Dt​[i+
1]
  • aia_iai​에 --force를 사용한다. aia_iai​의 서브트리 전체가 해결되므로 비용은 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]
    [Ri]D_{t-1}[R_i]
    Dt−1​[Ri​]
    O(N)O(N)O(N)