Deducing Salaries

The Byteotian Software Corporation (BSC) has \(n\) employees arranged in a strict hierarchy. Every employee (except the CEO) has a direct supervisor and every employee has a unique monthly salary that is a permutation of \(\{1, 2, \dots, n\}\). In particular, if we denote the salary of employee \(i\) by \(a_i\), then

[ {a_1,a_2,\dots,a_n} = {1,2,\dots,n}, ]

and every supervisor earns strictly more than each of their subordinates. Some employees have their salaries publicly disclosed; that is, for some indices \(i\) we know \(a_i\). Moreover, according to Byteotian law, if an employee's salary is disclosed then the salary of their supervisor is also disclosed.

Before the Byteotian Internal Revenue Anti-Corruption Service (BIRAS) storms the company, they wish to deduce all salaries that are not disclosed but can be uniquely determined from the disclosed ones together with the above constraints. In other words, an employee \(i\) with undisclosed salary gets a deduced value if in every valid completion (i.e. every permutation \(\{1,2,\dots, n\}\) that satisfies the condition that every supervisor earns more than their subordinate and is consistent with the disclosed salaries) the value \(a_i\) is the same. Otherwise, it remains unknown (and you should output 0 for that employee).

Note on the hierarchy and constraints:

• The hierarchy is given as a rooted tree. The CEO has no supervisor (its supervisor is denoted by 0 in the input).
• If an employee \(i\) has supervisor \(p_i\) (with \(p_i \neq 0\)), then it must hold that \(a_{p_i} > a_i\).
• The disclosed salaries are fixed; all others are initially 0. However, by considering the set \(S = \{1,2,\dots,n\} \setminus \{\text{disclosed salaries}\}\) and the constraints induced on each subtree, sometimes the unknown salaries can be uniquely deduced. A key observation is that if for some employee \(v\) (with unknown salary) the number of unknown employees in its subtree equals the count of available salary numbers in the open interval \((L, R)\) (where \(L\) is the maximum salary appearing in already determined descendants of \(v\) and \(R\) is the salary of \(v\)'s supervisor, or \(n+1\) if \(v\) is the CEO), then the assignment in that entire subtree is forced. In particular, \(v\)’s own salary must be the maximum number in that interval.</p>

  Your task is to output the deduced salaries for employees 1 through \(n\). For employees whose salary remains undetermined (i.e. there exists more than one valid possibility), output 0.

  inputFormat

  The input consists of three lines:

  1. An integer \(n\) \((1 \le n \le 10^5)\) denoting the number of employees.
  2. \(n\) space‐separated integers \(a_1, a_2, \dots, a_n\). If \(a_i = 0\) then the salary of employee \(i\) is not disclosed; otherwise, it is the disclosed salary \(a_i\) \( (1 \le a_i \le n)\).
  3. \(n\) space‐separated integers \(p_1, p_2, \dots, p_n\) where for each employee \(i\), \(p_i = 0\) if \(i\) is the CEO and otherwise \(p_i\) is the direct supervisor of employee \(i\). It is guaranteed that if \(a_i \neq 0\) then \(a_{p_i} \neq 0\) (i.e. the supervisor’s salary is disclosed).

  outputFormat

  Output a single line with \(n\) space‐separated integers. For each employee \(i\), output the deduced salary if it can be uniquely determined, or 0 otherwise.

  sample

  3
  3 0 0
  0 1 1

  3 0 0