DOJ logoDOJ
問題
最近追加された問題保存した問題Workbooks
カテゴリDLCコンテストグループチーム掲示板
ランキング
正解数ランキングストリークランキングDOJ Powerランキング
提出状況
問題募集ログイン新規登録
DOJ logoDOJ

OI形式のサブタスク採点、Eloレーティング、Discord連携を備えたオンラインジャッジです。

問題
問題一覧カテゴリ
コミュニティ
コンテストランキング掲示板お知らせ外部のコンテストを開催するガイド
アカウント
ログイン新規登録ジャッジ状態
ポリシー
利用規約DLCの利用規則プライバシーAPI 文書言語ランタイムコンテストの順位報酬レーティングとパフォーマンス
© 2026 DOJ
All rights reserved
解説

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)