Overview

This problem asks us to determine salary ranks for each employee in a tree-structured organization such that each rank is at least their parent’s rank and at most their upper limit, while maximizing the total sum.

The maximum rank each employee can take is determined by “the minimum upper limit rank within that employee’s subtree.”

Analysis

Let \(x_v\) be the salary rank of employee \(v\).

From the conditions, for any employee \(w\) contained in employee \(v\)’s subtree (i.e., subordinates of \(v\) or their further subordinates),

\[ x_v \leq x_w \]

holds.

Also, since each employee \(w\) has an upper limit \(U_w\),

\[ x_w \leq U_w \]

Therefore, the salary rank \(x_v\) of employee \(v\) must be at most the upper limit of every employee in the subtree.

That is,

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

Letting this value be \(M_v\), the maximum value that can be assigned as employee \(v\)’s salary rank is \(M_v\).

Since we want to maximize the total, we should basically assign each employee the largest possible value, namely \(M_v\).

However, the salary rank of employee \(1\) (the president) is always \(1\).

Therefore, for the overall assignment to be feasible, the upper limit of every employee must be at least \(1\). This can be checked by:

\[ M_1 \geq 1 \]

If \(M_1 < 1\), then some employee’s upper limit is \(0\), making it impossible to assign a positive integer rank.

Problem with the Naive Approach

If we “examine the entire subtree for each employee to find the minimum,” it takes \(O(N^2)\) in the worst case.

For example, if the tree is a straight line, the sum of subtree sizes for each employee is:

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

Since \(N \leq 2 \times 10^5\), this won’t be fast enough.

Instead, we propagate the minimum upper limit from children to parents, processing the entire tree in \(O(N)\).

Algorithm

First, for each employee \(i\), initialize:

\[ mn_i = U_i \]

Then, process employees in decreasing order of their employee number.

By the constraints, the supervisor \(P_i\) of employee \(i\) always has a smaller number than \(i\).

This means that by processing in decreasing order of employee number, we can propagate information from descendants to ancestors.

If \(mn_i\) is the minimum upper limit within employee \(i\)’s subtree, then this value is also contained in parent \(P_i\)’s subtree, so we update:

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

By performing this for \(i=N,N-1,\dots,2\), the final \(mn_i\) becomes the minimum upper limit among all employees in employee \(i\)’s subtree.

Then:

• If \(mn_1 < 1\), it’s impossible, so output \(-1\)
• Otherwise, the president gets rank \(1\)
• Employees \(2\) and beyond are each assigned \(mn_i\)

This maximizes the total.

The answer is:

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

The reason this assignment satisfies the conditions is that since a child’s subtree is contained within the parent’s subtree,

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

holds.

Therefore, a child’s salary rank is always at least the parent’s salary rank.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

Since parent \(P_i\) is always smaller than \(i\), processing employee numbers in reverse order from \(N\) to \(2\) correctly propagates subtree minimums to parents.

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

Also, since the upper limit \(U_i\) can be up to \(10^9\) and there can be up to \(2 \times 10^5\) employees, the total can reach:

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

Therefore, the answer and upper limit values must be handled with long long type.

Source Code

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

---

This editorial was generated by gpt-5.5-high.