Sum of Prefix Sums
Contest: Educational Codeforces Round 82 (Rated for Div. 2)
Difficulty rating: 2700
Tags: data structures, divide and conquer, geometry, trees

We define the sum of prefix sums of an array $$$[s_1, s_2, \dots, s_k]$$$ as $$$s_1 + (s_1 + s_2) + (s_1 + s_2 + s_3) + \dots + (s_1 + s_2 + \dots + s_k)$$$.

You are given a tree consisting of $$$n$$$ vertices. Each vertex $$$i$$$ has an integer $$$a_i$$$ written on it. We define the value of the simple path from vertex $$$u$$$ to vertex $$$v$$$ as follows: consider all vertices appearing on the path from $$$u$$$ to $$$v$$$, write down all the numbers written on these vertices in the order they appear on the path, and compute the sum of prefix sums of the resulting sequence.

Your task is to calculate the maximum value over all paths in the tree.

Input format:
The first line contains one integer $$$n$$$ ($$$2 \le n \le 150000$$$) — the number of vertices in the tree.

Then $$$n - 1$$$ lines follow, representing the edges of the tree. Each line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$), denoting an edge between vertices $$$u_i$$$ and $$$v_i$$$. It is guaranteed that these edges form a tree.

The last line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^6$$$).

Output format:
Print one integer — the maximum value over all paths in the tree.

Constraints:
Time limit: 6.0 s
Memory limit: 512.0 MB

Note:
The best path in the first example is from vertex $$$3$$$ to vertex $$$1$$$. It gives the sequence $$$[3, 3, 7, 1]$$$, and the sum of prefix sums is $$$36$$$.

Example input:
4
4 2
3 2
4 1
1 3 3 7

Example output:
36

Editorial:
Let's use centroid decomposition to solve the problem. We need to process all the paths going through each centroid somehow.
Consider a path from vertex $$$u$$$ to vertex $$$v$$$ going through vertex $$$c$$$, which is an ancestor of both $$$u$$$ and $$$v$$$ in the centroid decomposition tree. Suppose the sequence of numbers on path from $$$u$$$ to $$$c$$$ (including both these vertices) is $$$[a_1, a_2, \dots, a_k]$$$, and the sequence of numbers on path from $$$c$$$ to $$$v$$$ (including $$$v$$$, but excluding $$$c$$$) is $$$[b_1, b_2, \dots, b_m]$$$. Let $$$sum_a = \sum\limits_{i = 1}^{k} a_i$$$, $$$psum_a = \sum\limits_{i = 1}^{k} (k - i + 1) a_i$$$, and $$$psum_b = \sum\limits_{i = 1}^{m} (m - i + 1) b_i$$$. We can show that the sum of prefix sums of $$$[a_1, a_2, \dots, a_k, b_1, b_2, \dots, b_m]$$$ is equal to $$$psum_a + psum_b + sum_a \cdot m$$$.
Now, suppose we fix the second part of the path ($$$psum_b$$$ and $$$m$$$ are fixed), and we want to find the best first part for this second part. Each possible first part is represented by a linear function, and our goal is to find the maximum over all these linear functions in the point $$$m$$$, and add $$$psum_b$$$ to this maximum. This can be done with the help of convex hull or Li Chao tree.
The most difficult part of implementation is how to process each centroid's subtree. It's easy to obtain all "first parts" and "second parts" of paths going through the centroid, but pairing them up can be complicated — for each second part, we have to build a convex hull or Li Chao tree on all first parts going to this centroid, excluding those which go through the same child of the centroid as the "second part" we are considering. One of the best ways to implement this is the following. Suppose our centroid has $$$m$$$ children, $$$fp_i$$$ is the set of "first parts" going from the $$$i$$$-th child of the centroid, and $$$sp_i$$$ is the set of "second parts" going to the $$$i$$$-th child. We will create a new data structure (initially empty), process all second parts from $$$sp_1$$$, add all first parts from $$$fp_1$$$, process all second parts from $$$sp_2$$$, add all first parts from $$$fp_2$$$, and so on. After that, we will clear our data structure, process all second parts from $$$sp_m$$$, add all first parts from $$$fp_m$$$, process all second parts from $$$sp_{m - 1}$$$, add all first parts from $$$fp_{m - 1}$$$, and so on, until we add all first parts from $$$fp_1$$$. That way we will consider all possible first parts for each second part we are trying to use.