codeforces-scrape

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

1997D.md (1978B)


      1 Source: https://codeforces.com/problemset/problem/1997/D
      2 
      3 D. Maximize the Root
      4 
      5 time limit per test
      6 
      7 3 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 You are given a rooted tree, consisting of $n$ vertices. The vertices in the tree are numbered from $1$ to $n$, and the root is the vertex $1$. The value $a_i$ is written at the $i$-th vertex.
     22 
     23 You can perform the following operation any number of times (possibly zero): choose a vertex $v$ which has at least one child; increase $a_v$ by $1$; and decrease $a_u$ by $1$ for all vertices $u$ that are in the subtree of $v$ (except $v$ itself). However, after each operation, the values on all vertices should be non-negative.
     24 
     25 Your task is to calculate the maximum possible value written at the root using the aforementioned operation.
     26 
     27 Input
     28 
     29 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     30 
     31 The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of vertices in the tree.
     32 
     33 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$) — the initial values written at vertices.
     34 
     35 The third line contains $n-1$ integers $p_2, p_3, \dots, p_n$ ($1 \le p_i \le n$), where $p_i$ is the parent of the $i$-th vertex in the tree. Vertex $1$ is the root.
     36 
     37 Additional constraint on the input: the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.
     38 
     39 Output
     40 
     41 For each test case, print a single integer — the maximum possible value written at the root using the aforementioned operation.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 3
     49 
     50 4
     51 
     52 0 1 0 2
     53 
     54 1 1 3
     55 
     56 2
     57 
     58 3 0
     59 
     60 1
     61 
     62 5
     63 
     64 2 5 3 9 6
     65 
     66 3 1 5 2
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 1
     73 3
     74 6
     75 ```
     76 
     77 Note
     78 
     79 In the first test case, the following sequence of operations is possible:
     80 
     81 * perform the operation on $v=3$, then the values on the vertices will be $[0, 1, 1, 1]$;
     82 * perform the operation on $v=1$, then the values on the vertices will be $[1, 0, 0, 0]$.