유량 찾기

지난 여름, 지도 제작자 Carla는 국립 측위 및 지도 제작 센터(NCPC)를 대표하여 탐사를 떠났다. 목표는 북쪽 멀리 떨어진 하천계의 물의 흐름을 측정하는 것이었다. 그러나 그 지역은 매우 외딴 곳이고 Carla는 모험을 즐기는 성격이 아니라서 일부 지점의 물의 흐름만 측정할 수 있었다. Carla는 NCPC가 내년 여름에 자신을 다시 이 야생으로 보낼까 걱정되어, 누락된 데이터를 복원할 수 있는지 알아보기 위해 몇몇 알고리즘 전문가(여러분)에게 자문을 구했다.

하천계는 1번부터 n번까지 번호가 매겨진 n개의 정점을 가진 뿌리 있는 트리로 표현된다. 이 트리의 잎은 수원이고, 나머지 정점은 합류점(여러 강이 합쳐지는 지점)에 해당한다. 물은 번호가 큰 정점에서 번호가 작은 정점으로 흐른다. 트리의 뿌리인 정점 1은 하천계가 바다로 흘러드는 하구이다. 수원의 물의 흐름은 임의의 양의 정수일 수 있고, 합류점의 물의 흐름은 자식들의 물의 흐름의 합이다. 이 트리와 일부 정점의 물의 흐름이 주어질 때, 모든 정점의 물의 흐름을 구하거나 그것이 불가능함을 판정하는 것이 과제이다.

그림 F.1: 예제 입력 1과 그 해답의 그림. 물은 왼쪽에서 오른쪽으로 흐른다. 정점 1, 5, 7, 9의 흐름은 빨간색으로 표시되어 있으며, 주어지지 않았지만 각각 9, 2, 3, 1로 추론할 수 있다.

입력의 첫째 줄에는 트리의 정점 수 n (2 ≤ n ≤ 3 · 10^5)이 주어진다. 다음 줄에는 n − 1개의 정수 p2, . . . , pn (1 ≤ pi < i)이 주어지며, pi는 정점 i의 부모의 번호이다.

마지막으로 n개의 정수 a1, . . . , an (0 ≤ ai ≤ 10^9)이 한 줄에 주어지며, ai는 정점 i의 물의 흐름을 나타낸다. ai가 0이면 그 정점의 물의 흐름은 알 수 없다. 그렇지 않으면 ai는 정점 i의 물의 흐름과 같다. ai의 상한 10^9는 알 수 없는 값에는 적용되지 않으며, 알 수 없는 값은 임의의 양의 정수일 수 있다.

n개의 물의 흐름을 모두 유일하게 복원할 수 있으면 정점 번호가 증가하는 순서로 출력한다. 그렇지 않으면 “impossible”을 출력한다. 물의 흐름을 복원하는 방법이 아예 없을 수도 있으며(Carla가 제공한 데이터가 어딘가 모순인 경우), 그 경우에도 “impossible”을 출력해야 한다.