概要

本問題は、木構造で表される組織において、与えられた制約（上司の給与ランク以上、上限ランク以下、社長は \(1\) 固定）を満たしつつ、全員の給与ランクの合計を最大化する問題です。

考察

1. 制約の言い換え

問題の条件を整理してみましょう。 - 社長（社員 \(1\)）の給与ランク \(R_1\) は \(1\)。 - 各社員 \(i\) の給与ランク \(R_i\) は、直属の上司 \(P_i\) の給与ランク \(R_{P_i}\) 以上（ \(R_i \geq R_{P_i}\) ）。 - 各社員 \(i\) の給与ランク \(R_i\) は、上限 \(U_i\) 以下（ \(R_i \leq U_i\) ）。

ここで、2つ目の条件「部下の給与ランクは上司以上」に注目します。これは、「上司の給与ランクは、部下の給与ランク以下」と言い換えることができます。 さらに、部下の給与ランクは部下自身の上限以下でなければならないため、間接的に「上司の給与ランクは、すべての子孫（部下やそのさらに部下）の上限ランク以下」でなければならないことが分かります。

例えば、上司 \(A\) の部下に \(B\) がおり、\(B\) の上限が \(U_B = 5\) だったとします。 もし \(A\) の給与ランクを \(6\) にしてしまうと、\(B\) の給与ランクは \(A\) 以上（ \(6\) 以上）かつ \(B\) の上限以下（ \(5\) 以下）にする必要があり、これは不可能です。したがって、 \(A\) の給与ランクは \(5\) 以下でなければなりません。

2. 実質的な上限ランクの計算

この考察から、各社員 \(i\) の「実質的な上限ランク」を \(U'_i\) とすると、これは以下のように定義できます。 - \(U'_i = \min( U_i, \text{すべての直属の部下 } j \text{ の } U'_j )\)

この \(U'_i\) を、組織の末端（葉）から社長（根）に向かって順番に更新していくことで、すべての社員の実質的な上限ランクを求めることができます。

3. 合計の最大化

実質的な上限ランク \(U'_i\) を求めたあと、給与ランクの合計を最大化するには、各社員に許される最大の給与ランクを割り当てるのが最適です。 - 社員 \(1\) （社長）の給与ランクは \(1\) で固定です。 - 社員 \(i\) （ \(i \geq 2\) ）の給与ランクは、上限いっぱいの \(U'_i\) とします。

この割り当てが常に条件を満たすことは、 \(U'_{P_i} \leq U'_i\) が成り立つことから保証されます。

ただし、社長の実質的な上限ランク \(U'_1\) が \(1\) 未満になってしまった場合は、社長に給与ランク \(1\) を割り当てることができないため、条件を満たす割り当ては存在せず、答えは \(-1\) となります。

アルゴリズム

1. 上限値の逆方向伝播: 木の葉から根の方向へ上限値を伝播させます。 問題の制約から、上司の番号は常に自身の番号より小さい（ \(P_i < i\) ）ため、トポロジカルソートなどの複雑なアルゴリズムを使わずとも、\(i = N\) から \(2\) まで逆順にループを回すだけで、葉から根への正しい順序で更新が行えます。 具体的には、各 \(i\) について \(U_{P_i} = \min(U_{P_i}, U_i)\) と更新します。

2. 判定と出力:

   • 更新後の \(U_1 < 1\) であれば、条件を満たす割り当てが存在しないため -1 を出力します。
   • そうでなければ、合計値 \(1 + \sum_{i=2}^{N} U_i\) を出力します。

計算量

• 時間計算量: \(O(N)\) \(N\) から \(2\) までの逆順ループを \(1\) 回行うだけなので、非常に高速に動作します。
• 空間計算量: \(O(N)\) 社員の上限ランク \(U\) と上司の配列 \(P\) を保持するための配列サイズのみが必要です。

実装のポイント

• 親のインデックスの関係性: \(P_i < i\) という制約があるため、単純な for (int i = N; i >= 2; --i) ループで木を後ろから辿るだけで、親へ正しく最小値が伝播します。

• オーバーフローの防止: 給与ランクの合計値は、最大で \(N \times \max(U_i) \approx 2 \times 10^5 \times 10^9 = 2 \times 10^{14}\) に達するため、答えを格納する変数 ans は 32-bit 整数型（int）ではなく 64-bit 整数型（C++では long long）を使用する必要があります。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    vector<long long> U(N + 1);
    vector<int> P(N + 1);

    cin >> U[1];

    for (int i = 2; i <= N; ++i) {
        cin >> P[i] >> U[i];
    }

    // トポロジカルソートの逆順（葉から根の方向）に上限値を伝播させる
    // P_i < i であるため、N から 2 まで逆順にループを回すだけで正しく伝播する
    for (int i = N; i >= 2; --i) {
        U[P[i]] = min(U[P[i]], U[i]);
    }

    // 社員 1 の給与ランクは 1 固定。
    // もし U[1] が 1 未満になってしまった場合、条件を満たす割り当ては存在しない
    if (U[1] < 1) {
        cout << -1 << "\n";
        return 0;
    }

    // 各社員 i (i >= 2) の給与ランクの最大値は、更新後の U[i] となる
    long long ans = 1; // 社員 1 の給与ランクは 1
    for (int i = 2; i <= N; ++i) {
        ans += U[i];
    }

    cout << ans << "\n";

    return 0;
}

---

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