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]$.