codeforces-scrape

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

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  ![](https://espresso.codeforces.com/ca9befad93e279ba6473c3a326b02cf92524400c.png) 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$.