시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB77423670.588%

문제

$N$개의 정점으로 구성된 루트 있는 트리가 있다. 각 정점은 $1$번부터 $N$번까지 번호가 매겨져 있고, 각 정점에는 $0$ 이상 $N$ 미만의 정수 값이 적혀 있다.

주어진 트리에서 모든 정점에 대해 $mex(i)$를 구해야 한다. $mex(i)$는 $i$번 정점을 루트로 하는 서브 트리의 정점에 적혀 있지 않은 수 중에서 가장 작은 음이 아닌 정수이다.

$1$이상 $N$이하의 모든 정수 $i$에 대해 $mex(i)$를 출력하여라.

입력

첫째 줄에 정점의 수 $N$이 주어진다. $(1 \leq N \leq 200\,000)$

둘째 줄에 $1$번 정점부터 $N$번 정점까지 각 정점의 부모 정점의 번호 $p_i$가 주어진다. 만약 부모 정점이 없다면 대신 $-1$이 주어진다. 입력으로 주어지는 그래프는 트리임이 보장된다.

셋째 줄에 $1$번 정점부터 $N$번 정점까지 각 정점에 적힌 값 $v_i$가 주어진다. $(0 \leq v_i < N)$

출력

$N$개의 줄에 걸처 각 정점의 $mex(i)$를 출력한다. $i$번째 줄에는 $mex(i)$를 출력한다.

예제 입력 1

9
-1 1 6 9 2 1 9 9 6
3 1 2 4 0 2 1 0 0

예제 출력 1

5
2
0
0
1
3
0
1
2

출처

University > POSTECH > 2022 POSTECH Programming Contest F번