Overview

We assign salary ranks to each employee in a tree structure such that each rank is at least as large as their parent’s rank and at most their own upper limit.
The president’s salary rank is fixed at \(1\), and we want to maximize the total sum of all employees’ salary ranks.

Analysis

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

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

\[ x_v \leq x_w \leq U_w \]

must hold.

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

In other words,

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

Here, we define

\[ mn_v = \min_{w \in \text{subtree}(v)} U_w \]

Then, the maximum salary rank that can be assigned to employee \(v\) is \(mn_v\).

However, only the president has their salary rank fixed at \(1\).
Therefore, it is optimal to assign the maximum value \(mn_v\) to every employee other than the president.

This works because \(mn_v\) is the upper bound that employee \(v\) can take, and since it is the minimum value in the subtree, the parent-child relationship naturally satisfies

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

This holds because the parent’s subtree contains the child’s subtree, so the minimum on the parent’s side is at most the minimum on the child’s side.

For example, if the upper limits in an employee’s subtree are \([10, 7, 3]\), then that employee’s salary rank can be at most \(3\).
Even if the employee’s own upper limit is \(10\), if there is a subordinate below with an upper limit of \(3\), setting this employee to \(4\) or more would force that subordinate to also be \(4\) or more, which violates the conditions.

Naively “setting each employee to their own upper limit \(U_i\)” may fail to satisfy the parent-child relationship.
Therefore, we need to compute the “minimum upper limit across the entire subtree” for each employee.

Algorithm

For each employee \(v\), we compute the minimum upper limit rank \(mn_v\) within their subtree.

The input guarantees \(P_i < i\).
That is, a parent’s index is always smaller than its child’s.

Therefore, by iterating employee indices in reverse order from \(N\) down to \(2\), we can propagate information from children to parents.

Specifically, we first initialize

\[ mn_i = U_i \]

Then, for each employee \(i\) from \(N\) down to \(2\), letting the parent be \(p = P_i\), we update

\[ mn_p = \min(mn_p, mn_i) \]

As a result, \(mn_i\) ultimately becomes the minimum upper limit rank among all employees in the subtree of employee \(i\).

Finally, since the president’s salary rank is fixed at \(1\), if

\[ mn_1 < 1 \]

then either the president or someone else has an upper limit of \(0\), making it impossible to assign a positive integer salary rank.
In this case, we output \(-1\).

Otherwise, the maximum total is

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

The president is assigned \(1\), and every other employee \(i\) is assigned \(mn_i\).

Complexity

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

Implementation Notes

• Since \(P_i < i\), there is no need to build an adjacency list and perform DFS.

• By processing employee indices in reverse order, we can propagate the subtree minimum from children to parents.

• The answer can be as large as approximately \(2 \times 10^5 \times 10^9\), so while this is not an issue in Python, other languages require a 64-bit integer type.

• In the code, mn[i] ultimately represents “the minimum upper limit rank within the subtree of employee \(i\).”

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N = data[0]

    parent = [0] * (N + 1)
    mn = [0] * (N + 1)

    idx = 1
    mn[1] = data[idx]
    idx += 1

    for i in range(2, N + 1):
        parent[i] = data[idx]
        mn[i] = data[idx + 1]
        idx += 2

    for i in range(N, 1, -1):
        p = parent[i]
        if mn[i] < mn[p]:
            mn[p] = mn[i]

    if mn[1] < 1:
        print(-1)
    else:
        print(1 + sum(mn[2:]))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.