직원 급여 추론

시간 제한1초메모리 제한128 MB

요약

뿌리 쪽으로 갈수록 커지는 1부터 n까지의 순열 급여를 가진 트리에서 일부 값이 공개되어 있을 때, 반드시 정해지는 급여만 출력하고 나머지는 0을 출력한다.

난이도: 어려움10점 중 8점
유형: 트리, 그리디, 누적 합, 구현
정답자: 아직 제출이 없습니다

문제

한 회사에 직원 $n$ 명이 있으며 엄격한 계층 구조를 이룹니다. CEO를 제외한 모든 직원은 직속 상사가 정확히 한 명 있고, CEO는 나머지 모든 직원의 (직접 또는 간접) 상사입니다. 각 직원의 월급은 서로 다르며 $1$ 부터 $n$ 까지의 정수가 정확히 한 번씩 배정됩니다. 모든 상사는 자신의 부하 직원보다 반드시 더 많은 급여를 받습니다.

일부 급여는 공개되어 있습니다. 법에 따라 어떤 직원의 급여가 공개되면 그 직속 상사의 급여도 함께 공개됩니다.

공개된 급여와 계층 구조만으로 유일하게 결정되는, 아직 공개되지 않은 급여를 모두 구하세요.

입력

첫 줄에 직원 수 $n$ ( $1 \le n \le 10^6$ )이 주어집니다. 직원 번호는 $1$ 부터 $n$ 까지입니다.

이어지는 $n$ 개의 줄 중 $i+1$ 번째 줄은 직원 $i$ 를 설명하며, 두 정수 $p_i$ 와 $z_i$ ( $1 \le p_i \le n$ , $0 \le z_i \le n$ )가 공백으로 구분되어 주어집니다. $p_i$ 는 직원 $i$ 의 직속 상사 번호이고, $p_i = i$ 이면 직원 $i$ 가 CEO입니다. $z_i > 0$ 이면 그 값이 직원 $i$ 의 공개된 급여이고, $z_i = 0$ 이면 급여가 공개되지 않았습니다. 양수인 $z_i$ 는 모두 서로 다릅니다.

입력은 항상 일관적이어서, 계층 구조와 공개된 값에 모순되지 않는 급여 배정이 적어도 하나 존재합니다.

출력

$n$ 개의 줄을 출력합니다. $i$ 번째 줄에는 직원 $i$ 의 급여가 공개되어 있거나 공개된 급여로부터 유일하게 추론될 수 있으면 그 급여를, 그렇지 않으면 $0$ 을 출력합니다.

예제4

예제 1

입력

예상 출력

예제 2
입력
```
1
1 0
```
예상 출력
```
1
```
예제 3
입력
```
6
1 0
1 0
2 0
3 0
4 0
5 0
```
예상 출력
```
6
5
4
3
2
1
```
예제 4
입력
```
6
1 6
1 0
1 0
1 0
1 0
1 0
```
예상 출력
```
6
0
0
0
0
0
```