Teto's Emotions#12449
Teto is composing a song.
The song can be represented as a tree with fragments. Each fragment is a vertex of the tree, and the edges show how the fragments are connected to each other. For each fragment , its emotional value a_i is given.
Teto must choose exactly one fragment as the central fragment of the song.
After that, all fragments whose distance from is exactly are removed from the song. All edges incident to these fragments are also removed.
The chosen fragment itself is not removed.
After the removal, the tree may split into several connected components. For each such component, we calculate the sum of emotional values of all fragments that remain in it.
Let these sums be c_1, c_2, \ldots, c_k, where is the number of connected components after the removal.
The contrast of choosing fragment is defined as the value , where
D = \max(c_1, c_2, \ldots, c_k) - \min(c_1, c_2, \ldots, c_k).
Find the maximum possible contrast over all ways to choose the central fragment .
The first line contains one integer (1 \le n \le 2 \cdot 10^5) — the number of fragments in the song.
The second line contains integers a_1, a_2, \ldots, a_n (-10^9 \le a_i \le 10^9) — the emotion values of the fragments.
Each of the next n-1 lines contains two integers and (1 \le u, v \le n,\ u \ne v) — an edge of the tree.
It is guaranteed that the given graph is a tree.
Output a single integer — the maximum possible contrast over all choices of the central fragment .
Example 1
Example 2
In the first example, it is optimal to choose fragment v = 4 as the central fragment. Then fragment is at distance exactly from it, so it is deleted.
After the deletion, two connected components remain:
with sum ;
\{3, 4, 5\} with sum 3 + 4 + 5 = 12.
Therefore, the contrast is 12 - 1 = 11.
In the second example, it is optimal to choose fragment v = 2 as the central fragment. Then fragment is at distance exactly from it, so it is deleted.
After the deletion, three connected components remain:
\{1, 2, 4, 5\} with sum 5 + (-2) + 10 + (-3) = 10;
with sum ;
with sum .
Therefore, the contrast is 10 - (-6) = 16.
Subtask ( points): n \le 10.
Subtask ( points): n \le 5000.
Subtask ( points): the tree is a path.
Subtask ( points): a_i = 1 for all 1 \le i \le n.
Subtask ( points): |a_i| \le 1 for all 1 \le i \le n.
Subtask ( points): a_i \ge 0 for all 1 \le i \le n.
Subtask ( points): No additional constraints.