시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 284 | 126 | 98 | 44.749% |
$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)$를 출력한다.
9 -1 1 6 9 2 1 9 9 6 3 1 2 4 0 2 1 0 0
5 2 0 0 1 3 0 1 2
University > POSTECH > 2022 POSTECH Programming Contest F번