概要

木構造の各社員に、親以上・自身の上限以下となる給与ランクを割り当てます。
社長の給与ランクは \(1\) に固定されている中で、全員の給与ランクの合計を最大化します。

考察

社員 \(v\) の給与ランクを \(x_v\) とします。

条件より、ある社員 \(v\) とその部下・さらにその部下、つまり \(v\) の部分木に含まれる任意の社員 \(w\) について、

\[ x_v \leq x_w \leq U_w \]

が成り立ちます。

したがって、社員 \(v\) の給与ランク \(x_v\) は、自分自身を含む部分木内の全員の上限ランク以下でなければなりません。

つまり、

\[ x_v \leq \min_{w \in \text{subtree}(v)} U_w \]

です。

ここで、

\[ mn_v = \min_{w \in \text{subtree}(v)} U_w \]

と定義します。

すると、社員 \(v\) に設定できる給与ランクの最大値は \(mn_v\) です。

ただし、社長だけは給与ランクが \(1\) に固定されています。
そのため、社長以外の社員はそれぞれ最大である \(mn_v\) を割り当てるのが最適です。

なぜなら、\(mn_v\) は社員 \(v\) が取り得る上限であり、さらに部分木の最小値なので、親子関係についても自然に

\[ mn_{\text{parent}} \leq mn_{\text{child}} \]

が成り立ちます。

これは、親の部分木は子の部分木を含んでいるため、親側の最小値は子側の最小値以下になるからです。

例えば、ある社員の部分木の上限が \([10, 7, 3]\) なら、その社員の給与ランクは最大でも \(3\) です。
たとえ本人の上限が \(10\) でも、下の部下に上限 \(3\) の人がいるなら、その社員を \(4\) 以上にすると、その部下も \(4\) 以上にしなければならず、条件を満たせません。

素朴に「各社員を自分の上限 \(U_i\) にする」と、親子関係を満たせない場合があります。
そのため、各社員について「自分の部分木全体での最小上限」を求める必要があります。

アルゴリズム

各社員 \(v\) について、部分木内の上限ランクの最小値 \(mn_v\) を求めます。

入力では \(P_i < i\) が保証されています。
つまり、親の番号は必ず子より小さいです。

したがって、社員番号を \(N\) から \(2\) まで逆順に見ていけば、子の情報を親に伝えることができます。

具体的には、最初は

\[ mn_i = U_i \]

としておきます。

その後、社員 \(i\) を \(N\) から \(2\) まで見て、親を \(p = P_i\) とすると、

\[ mn_p = \min(mn_p, mn_i) \]

と更新します。

これにより、最終的に \(mn_i\) は社員 \(i\) の部分木に含まれる上限ランクの最小値になります。

最後に、社長の給与ランクは \(1\) に固定なので、もし

\[ mn_1 < 1 \]

なら、社長自身または誰かの上限が \(0\) であり、給与ランクを正の整数として割り当てられません。
この場合は \(-1\) を出力します。

そうでなければ、最大合計は

\[ 1 + \sum_{i=2}^{N} mn_i \]

です。

社長は \(1\)、それ以外の社員 \(i\) は \(mn_i\) を割り当てます。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• \(P_i < i\) なので、隣接リストを作って DFS する必要はありません。

• 社員番号を逆順に処理すれば、子から親へ部分木の最小値を伝播できます。

• 答えは最大で \(2 \times 10^5 \times 10^9\) 程度になるため、Python では問題ありませんが、他言語では 64 bit 整数型を使う必要があります。

• コード中の mn[i] は、最終的に「社員 \(i\) の部分木内の上限ランクの最小値」を表します。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N = data[0]

    parent = [0] * (N + 1)
    mn = [0] * (N + 1)

    idx = 1
    mn[1] = data[idx]
    idx += 1

    for i in range(2, N + 1):
        parent[i] = data[idx]
        mn[i] = data[idx + 1]
        idx += 2

    for i in range(N, 1, -1):
        p = parent[i]
        if mn[i] < mn[p]:
            mn[p] = mn[i]

    if mn[1] < 1:
        print(-1)
    else:
        print(1 + sum(mn[2:]))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-high によって生成されました。