1098A.md (1764B)
1 Source: https://codeforces.com/problemset/problem/1098/A 2 3 A. Sum in the tree 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Mitya has a rooted tree with $n$ vertices indexed from $1$ to $n$, where the root has index $1$. Each vertex $v$ initially had an integer number $a_v \ge 0$ written on it. For every vertex $v$ Mitya has computed $s_v$: the sum of all values written on the vertices on the path from vertex $v$ to the root, as well as $h_v$ — the depth of vertex $v$, which denotes the number of vertices on the path from vertex $v$ to the root. Clearly, $s_1=a_1$ and $h_1=1$. 22 23 Then Mitya erased all numbers $a_v$, and by accident he also erased all values $s_v$ for vertices with even depth (vertices with even $h_v$). Your task is to restore the values $a_v$ for every vertex, or determine that Mitya made a mistake. In case there are multiple ways to restore the values, you're required to find one which minimizes the total sum of values $a_v$ for all vertices in the tree. 24 25 Input 26 27 The first line contains one integer $n$ — the number of vertices in the tree ($2 \le n \le 10^5$). The following line contains integers $p_2$, $p_3$, ... $p_n$, where $p_i$ stands for the parent of vertex with index $i$ in the tree ($1 \le p_i \lt i$). The last line contains integer values $s_1$, $s_2$, ..., $s_n$ ($-1 \le s_v \le 10^9$), where erased values are replaced by $-1$. 28 29 Output 30 31 Output one integer — the minimum total sum of all values $a_v$ in the original tree, or $-1$ if such tree does not exist. 32 33 Examples 34 35 Input 36 37 ``` 38 5 39 1 1 1 1 40 1 -1 -1 -1 -1 41 ``` 42 43 Output 44 45 ``` 46 1 47 ``` 48 49 Input 50 51 ``` 52 5 53 1 2 3 1 54 1 -1 2 -1 -1 55 ``` 56 57 Output 58 59 ``` 60 2 61 ``` 62 63 Input 64 65 ``` 66 3 67 1 2 68 2 -1 1 69 ``` 70 71 Output 72 73 ``` 74 -1 75 ```