codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```