Overview

This problem involves an organization represented as a tree structure, where the goal is to maximize the total salary ranks of all employees while satisfying the given constraints (each employee’s rank must be at least their direct supervisor’s rank, at most their upper limit rank, and the president’s rank is fixed at \(1\)).

Analysis

1. Rephrasing the Constraints

Let’s organize the conditions of the problem. - The salary rank \(R_1\) of the president (employee \(1\)) is \(1\). - The salary rank \(R_i\) of each employee \(i\) must be at least the salary rank \(R_{P_i}\) of their direct supervisor \(P_i\) (\(R_i \geq R_{P_i}\)). - The salary rank \(R_i\) of each employee \(i\) must be at most their upper limit \(U_i\) (\(R_i \leq U_i\)).

Let’s focus on the second condition: “a subordinate’s salary rank is at least their supervisor’s.” This can be rephrased as “a supervisor’s salary rank must be at most their subordinate’s salary rank.” Furthermore, since a subordinate’s salary rank must be at most their own upper limit, we can indirectly deduce that “a supervisor’s salary rank must be at most the upper limit rank of all their descendants (subordinates, and their subordinates, etc.).”

For example, suppose supervisor \(A\) has a subordinate \(B\), and \(B\)’s upper limit is \(U_B = 5\). If we set \(A\)’s salary rank to \(6\), then \(B\)’s salary rank must be at least \(A\)’s (at least \(6\)) and at most \(B\)’s upper limit (at most \(5\)), which is impossible. Therefore, \(A\)’s salary rank must be at most \(5\).

2. Computing the Effective Upper Limit Rank

From this analysis, if we define the “effective upper limit rank” of each employee \(i\) as \(U'_i\), it can be defined as follows: - \(U'_i = \min( U_i, \text{all direct subordinates } j \text{'s } U'_j )\)

By updating \(U'_i\) sequentially from the leaves (bottom) of the organization toward the president (root), we can compute the effective upper limit ranks for all employees.

3. Maximizing the Total

After computing the effective upper limit ranks \(U'_i\), to maximize the total salary ranks, the optimal strategy is to assign each employee the maximum salary rank allowed. - Employee \(1\) (the president) has a fixed salary rank of \(1\). - Employee \(i\) (\(i \geq 2\)) is assigned the maximum possible salary rank of \(U'_i\).

This assignment always satisfies the constraints, which is guaranteed by the fact that \(U'_{P_i} \leq U'_i\) holds.

However, if the president’s effective upper limit rank \(U'_1\) becomes less than \(1\), then we cannot assign salary rank \(1\) to the president, meaning no valid assignment exists, and the answer is \(-1\).

Algorithm

1. Backward Propagation of Upper Limits: Propagate the upper limit values from the leaves toward the root of the tree. Due to the problem’s constraints, a supervisor’s index is always smaller than the employee’s own index (\(P_i < i\)), so without needing complex algorithms like topological sort, simply looping from \(i = N\) down to \(2\) correctly processes updates in leaf-to-root order. Specifically, for each \(i\), update \(U_{P_i} = \min(U_{P_i}, U_i)\).

2. Judgment and Output:

   • If \(U_1 < 1\) after the update, no valid assignment exists, so output -1.
   • Otherwise, output the total \(1 + \sum_{i=2}^{N} U_i\).

Complexity

• Time Complexity: \(O(N)\) Since we only perform a single reverse loop from \(N\) to \(2\), it runs very efficiently.
• Space Complexity: \(O(N)\) Only arrays to store the upper limit ranks \(U\) and the supervisor array \(P\) are needed.

Implementation Notes

• Parent Index Relationship: Due to the constraint \(P_i < i\), a simple for (int i = N; i >= 2; --i) loop traversing the tree from the back correctly propagates the minimum values to parents.

• Overflow Prevention: The total salary ranks can reach up to \(N \times \max(U_i) \approx 2 \times 10^5 \times 10^9 = 2 \times 10^{14}\), so the variable ans storing the answer must use a 64-bit integer type (long long in C++) rather than a 32-bit integer type (int).

  Source Code

#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;
}

---

This editorial was generated by gemini-3.5-flash-thinking.