2114E.md (2776B)
1 Source: https://codeforces.com/problemset/problem/2114/E 2 3 E. Kirei Attacks the Estate 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 Once, Kirei stealthily infiltrated the trap-filled estate of the Ainzbern family but was discovered by Kiritugu's familiar. Assessing his strength, Kirei decided to retreat. The estate is represented as a tree with $n$ vertices, with the root at vertex $1$. Each vertex of the tree has a number $a_i$ recorded, which represents the danger of vertex $i$. Recall that a tree is a connected undirected graph without cycles. 22 23 For a successful retreat, Kirei must compute the threat value for each vertex. The threat of a vertex is equal to the maximum alternating sum along the vertical path starting from that vertex. The alternating sum along the vertical path starting from vertex $i$ is defined as $a_i - a_{p_i} + a_{p_{p_i}} - \ldots$, where $p_i$ is the parent of vertex $i$ on the path to the root (to vertex $1$). 24 25 For example, in the tree below, vertex $4$ has the following vertical paths: 26 27 * $[4]$ with an alternating sum of $a_4 = 6$; 28 * $[4, 3]$ with an alternating sum of $a_4 - a_3 = 6 - 2 = 4$; 29 * $[4, 3, 2]$ with an alternating sum of $a_4 - a_3 + a_2 = 6 - 2 + 5 = 9$; 30 * $[4, 3, 2, 1]$ with an alternating sum of $a_4 - a_3 + a_2 - a_1 = 6 - 2 + 5 - 4 = 5$. 31 32  The dangers of the vertices are indicated in red. 33 34 Help Kirei compute the threat values for all vertices and escape the estate. 35 36 Input 37 38 The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 39 40 The following describes the test cases. 41 42 The first line contains an integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of vertices in the tree. 43 44 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the dangers of the vertices. 45 46 The next $n - 1$ lines contain the numbers $v, u$ ($1 \le v, u \le n$, $v \neq u$) — the description of the edges of the tree. 47 48 It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$. It is also guaranteed that the given set of edges forms a tree. 49 50 Output 51 52 For each test case, output $n$ integers — the threat of each vertex. 53 54 Example 55 56 Input 57 58 ``` 59 2 60 61 5 62 63 4 5 2 6 7 64 65 1 2 66 67 3 2 68 69 4 3 70 71 5 1 72 73 6 74 75 1000000000 500500500 900900900 9 404 800800800 76 77 3 4 78 79 5 1 80 81 2 5 82 83 1 6 84 85 6 4 86 ``` 87 88 Output 89 90 ``` 91 4 5 2 9 7 92 1000000000 1500500096 1701701691 199199209 404 800800800 93 ``` 94 95 Note 96 97 The tree from the first test case is depicted in the statement, and the maximum variable-sign sums are achieved as follows: 98 99 1. $a_1 = 4$; 100 2. $a_2 = 5$; 101 3. $a_3 = 2$; 102 4. $a_4 - a_3 + a_2 = 6 - 2 + 5 = 9$; 103 5. $a_5 = 7$.