概要

木構造の組織に対して、親以上・上限以下となるように各社員の給与ランクを決め、合計を最大化する問題です。

各社員が取り得る最大ランクは「その社員の部分木内にある上限ランクの最小値」で決まります。

考察

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

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

\[ x_v \leq x_w \]

が成り立ちます。

また、各社員 \(w\) には上限 \(U_w\) があるので、

\[ x_w \leq U_w \]

です。

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

つまり、

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

です。

この値を \(M_v\) とすると、社員 \(v\) の給与ランクとして設定できる最大値は \(M_v\) です。

合計を最大化したいので、基本的には各社員にできるだけ大きい値、つまり \(M_v\) を割り当てればよいです。

ただし、社長である社員 \(1\) の給与ランクは必ず \(1\) です。

そのため、全体として割り当てが可能であるためには、すべての社員の上限が少なくとも \(1\) である必要があります。これは、

\[ M_1 \geq 1 \]

で判定できます。

もし \(M_1 < 1\) なら、どこかの社員の上限が \(0\) であり、正の整数ランクを割り当てられないため不可能です。

素朴な方法の問題点

各社員について「その社員の部分木をすべて調べて最小値を求める」とすると、最悪の場合 \(O(N^2)\) かかります。

例えば、木が一直線になっている場合、各社員の部分木サイズの合計が

\[ N + (N-1) + \cdots + 1 = O(N^2) \]

となります。

\(N \leq 2 \times 10^5\) なので、これは間に合いません。

そこで、子から親へ上限の最小値を伝播させることで、全体を \(O(N)\) で処理します。

アルゴリズム

まず、各社員 \(i\) について、

\[ mn_i = U_i \]

としておきます。

その後、社員番号の大きい順に見ていきます。

制約より、社員 \(i\) の上司 \(P_i\) は必ず \(i\) より小さいです。

つまり、社員番号の大きい順に処理すれば、子孫側から親側へ情報を伝えることができます。

社員 \(i\) の部分木内の最小上限が \(mn_i\) だとすると、その値は親 \(P_i\) の部分木にも含まれるので、

\[ mn_{P_i} = \min(mn_{P_i}, mn_i) \]

と更新します。

これを \(i=N,N-1,\dots,2\) の順に行うと、最終的に \(mn_i\) は社員 \(i\) の部分木に含まれる上限ランクの最小値になります。

その後、

• \(mn_1 < 1\) なら不可能なので \(-1\)
• そうでなければ、社長はランク \(1\)
• 社員 \(2\) 以降はそれぞれ \(mn_i\) を割り当てる

とすれば合計最大になります。

答えは

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

です。

この割り当てが条件を満たす理由は、子の部分木は親の部分木に含まれるため、

\[ mn_{\text{親}} \leq mn_{\text{子}} \]

が成り立つからです。

したがって、子の給与ランクは親の給与ランク以上になります。

計算量

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

実装のポイント

親 \(P_i\) は必ず \(i\) より小さいため、社員番号を \(N\) から \(2\) へ逆順に処理すれば、部分木の最小値を親へ正しく伝播できます。

for (int i = N; i >= 2; i--) {
    mn[P[i]] = min(mn[P[i]], mn[i]);
}

また、上限 \(U_i\) は最大 \(10^9\)、社員数は最大 \(2 \times 10^5\) なので、合計値は最大で

\[ 2 \times 10^5 \times 10^9 = 2 \times 10^{14} \]

程度になります。

そのため、答えや上限値は long long 型で扱う必要があります。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

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

    cin >> mn[1];

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

    for (int i = N; i >= 2; i--) {
        mn[P[i]] = min(mn[P[i]], mn[i]);
    }

    if (mn[1] < 1) {
        cout << -1 << '\n';
        return 0;
    }

    long long ans = 1;
    for (int i = 2; i <= N; i++) {
        ans += mn[i];
    }

    cout << ans << '\n';
    return 0;
}

---

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