18023번 - Flow Finder 다국어

Last summer, Carla the Cartographer went on an expedition on behalf of the National Center for Positioning and Charting (the NCPC). The goal was to measure water flows of a river system far away in the north. However, the area is quite remote and Carla is not the adventurous type, so she was only able to measure the water flows in some of the locations. Carla is now worried that the NCPC will send her back to this wilderness next summer, so she consulted some algorithm experts (you) to see if it is possible to reconstruct the missing data.

The river system is represented by a rooted tree with n vertices numbered from 1 to n. The leaves of this tree are the sources, and the other vertices correspond to confluences (places where multiple rivers join together). Water flows from higher-numbered vertices to lower-numbered vertices. Vertex 1, the root of the tree, is the mouth of the river system, where it flows into the ocean. The water flow of a source can be any positive integer, while the water flow of a confluence is the sum of the water flows of its children. You will be given this tree along with the water flows at some of its vertices, and your task is to find the water flows at all the vertices or determine that this is impossible

Figure F.1: Illustration of Sample Input 1 and its solution. Water flows from left to right. The flows shown in red, from vertices 1, 5, 7 and 9, are not given but can be deduced to be 9, 2, 3 and 1 respectively

The first line of input contains an integer n (2 ≤ n ≤ 3 · 10⁵), the number of vertices in the tree. Then follows a line containing n − 1 integers p₂, . . . , p_n (1 ≤ p_i < i), where p_i is the number of the parent of vertex i.

Finally there is a line containing n integers a₁, . . . , a_n (0 ≤ a_i ≤ 10⁹), where a_i represents the water flow at vertex i. If a_i is equal to 0, then the water flow at that vertex is unknown. Otherwise, a_i is equal to the water flow at vertex i. Note that the upper bound 10⁹ on a_i does not apply to the unknown values, they can be any positive integer.

If all the n water flows can be reconstructed uniquely, then output them in increasing order of vertex number. Otherwise, output “impossible”. Note that it is possible that there is no way of reconstructing the water flows (if the data provided by Carla is inconsistent somehow). In that case you should also output “impossible”.