5/29/25, 3:28 PM Problem - 2114E - Codeforces
Enter | Register
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP
PROBLEMS SUBMIT STATUS STANDINGS CUSTOM TEST
Codeforces Round 1027 (Div. 3)
E. Kirei Attacks the Estate Finished
time limit per test: 2 seconds
memory limit per test: 256 megabytes → Virtual participation
Once, Kirei stealthily infiltrated the trap-filled estate of the Ainzbern family but was discovered by Virtual contest is a way to take part in past
contest, as close as possible to participation
Kiritugu's familiar. Assessing his strength, Kirei decided to retreat. The estate is represented as a
on time. It is supported only ICPC mode for
tree with n vertices, with the root at vertex 1. Each vertex of the tree has a number ai recorded, virtual contests. If you've seen these
problems, a virtual contest is not for you -
which represents the danger of vertex i . Recall that a tree is a connected undirected graph solve these problems in the archive. If you
without cycles. just want to solve some problem from a
contest, a virtual contest is not for you -
solve this problem in the archive. Never use
For a successful retreat, Kirei must compute the threat value for each vertex. The threat of a someone else's code, read the tutorials or
vertex is equal to the maximum alternating sum along the vertical path starting from that vertex. communicate with other person during a
virtual contest.
The alternating sum along the vertical path starting from vertex i is defined as
ai − ap + ap − …, where pi is the parent of vertex i on the path to the root (to vertex 1). Start virtual contest
i p
i
For example, in the tree below, vertex 4 has the following vertical paths:
[4] with an alternating sum of a4 = 6 ; → Problem tags
[4, 3] with an alternating sum of a4 − a3 = 6 − 2 = 4 ;
dfs and similar dp trees
[4, 3, 2] with an alternating sum of a4 − a3 + a2 = 6 − 2 + 5 = 9 ; No tag edit access
[4, 3, 2, 1] with an alternating sum of a4 − a3 + a2 − a1 = 6 − 2 + 5 − 4 = 5 .
→ Contest materials
Announcement
Tutorial
The dangers of the vertices are indicated in red.
Help Kirei compute the threat values for all vertices and escape the estate.
Input
The first line contains an integer t (1
4
≤ t ≤ 10 ) — the number of test cases.
The following describes the test cases.
The first line contains an integer n (2
5
≤ n ≤ 2 ⋅ 10 ) — the number of vertices in the tree.
9
The second line contains n integers a1 , a2 , … , an (1 ≤ ai ≤ 10 ) — the dangers of the
vertices.
The next n − 1 lines contain the numbers v, u (1 ,
≤ v, u ≤ n v ≠ u ) — the description of the
edges of the tree.
https://codeforces.com/problemset/problem/2114/E 1/2
5/29/25, 3:28 PM Problem - 2114E - Codeforces
5
It is guaranteed that the sum of n across all test cases does not exceed 2 ⋅ 10 . It is also
guaranteed that the given set of edges forms a tree.
Output
For each test case, output n integers — the threat of each vertex.
Example
input Copy
2
5
4 5 2 6 7
1 2
3 2
4 3
5 1
6
1000000000 500500500 900900900 9 404 800800800
3 4
5 1
2 5
1 6
6 4
output Copy
4 5 2 9 7
1000000000 1500500096 1701701691 199199209 404 800800800
Note
The tree from the first test case is depicted in the statement, and the maximum variable-sign
sums are achieved as follows:
1. a1 = 4 ;
2. a2 = 5 ;
3. a3 = 2 ;
4. a4 − a3 + a2 = 6 − 2 + 5 = 9 ;
5. a5 = 7 .
Codeforces (c) Copyright 2010-2025 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: May/29/2025 15:27:52UTC+6 (i1).
Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions
Supported by
https://codeforces.com/problemset/problem/2114/E 2/2
