概要

本問題は、木構造の関係を持つ社員に対して、いくつかの制約（社長のランクは \(1\)、部下のランクは上司以上、各社員の上限ランク以下）を満たしつつ、給与ランクの合計を最大化する問題です。

考察

給与ランクの合計を最大化するためには、各社員の給与ランクを可能な限り大きくしたいです。

直属の上司 \(P_i\) と部下 \(i\) の間には、給与ランク \(R\) について \(R_{P_i} \leq R_i\) という関係があります。 これは、視点を変えると「上司の給与ランクは、部下の給与ランク以下でなければならない」と言い換えることができます。

部下 \(i\) の給与ランクの上限が \(U_i\) であるため、上司 \(P_i\) の給与ランク \(R_{P_i}\) も \(U_i\) 以下に制限されます。 この関係を再帰的に適用すると、ある社員 \(u\) の給与ランクは、\(u\) の部下（子や孫など、自身を根とする部分木に含まれるすべての社員）の上限ランクの最小値以下でなければならないことが分かります。

したがって、各社員 \(i\) の「実質的な上限ランク」 \(U'_i\) を、自身を根とする部分木における \(U\) の最小値と定義します。

給与ランクの合計を最大化するためには、社長以外の社員 \(i \geq 2\) については、給与ランクをこの実質的な上限 \(U'_i\) と等しくするのが最適です。 社長（社員1）の給与ランクは \(1\) に固定されているため、以下の2つのケースに分かれます。

1. 社長の実質的な上限 \(U'_1\) が \(1\) 未満（すなわち \(0\)）の場合 社長の給与ランクを \(1\) にすることができないため、条件を満たす割り当ては存在せず、\(-1\) となります。
2. それ以外の場合 社長の給与ランクを \(1\)、それ以外の社員 \(i\) の給与ランクを \(U'_i\) とすることで、すべての制約を満たしつつ合計を最大化できます。 （部分木の最小値の定義から、上司 \(P_i\) の部分木は部下 \(i\) の部分木を内包するため、\(U'_{P_i} \leq U'_i\) が必ず成り立ち、制約を満たします）

アルゴリズム

各社員の実質的な上限 \(U'_i\) を効率よく求める必要があります。

制約 \(P_i < i\) より、社員の番号が大きい順に処理をすることで、自然と「葉から根（ボトムアップ）」の順に木を探索することができます。

1. 社員 \(i\) を \(N\) から \(2\) まで逆順にループします。
2. 社員 \(i\) の上限 \(U_i\) を用いて、その直属の上司 \(P_i\) の上限を \(U_{P_i} = \min(U_{P_i}, U_i)\) と更新します。
3. ループ終了後、\(U_1 < 1\) であれば -1 を出力します。
4. そうでなければ、社長の給与ランク \(1\) と、社員 \(2\) から \(N\) までの更新された上限 \(U_i\) の総和を出力します。

計算量

• 時間計算量: \(O(N)\) 逆順ループによるボトムアップの遷移は、各頂点について定数時間で行えるため、全体で \(O(N)\) となり非常に高速です。
• 空間計算量: \(O(N)\) 社員の上司情報 \(P\) と上限ランク \(U\) を保持するための配列のサイズに比例します。

実装のポイント

\(P_i < i\) というトポロジカルソートされたような性質が保証されているため、再帰を用いたDFS（深さ優先探索）や木DPを実装する必要がありません。単なる逆順の for ループ（range(N, 1, -1)）だけで簡潔かつ高速にボトムアップの遷移を実現できます。

ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    U = [0] * (N + 1)
    U[1] = int(input_data[1])
    
    P = [0] * (N + 1)
    idx = 2
    for i in range(2, N + 1):
        P[i] = int(input_data[idx])
        U[i] = int(input_data[idx+1])
        idx += 2
        
    for i in range(N, 1, -1):
        p = P[i]
        if U[i] < U[p]:
            U[p] = U[i]
            
    if U[1] < 1:
        print(-1)
    else:
        ans = 1 + sum(U[2:])
        print(ans)

if __name__ == '__main__':
    solve()

---

この解説は gemini-3.5-flash-thinking によって生成されました。