Alternating Tree
Contest: Divide by Zero 2018 and Codeforces Round 474 (Div. 1 + Div. 2, combined)
Difficulty rating: 2300
Tags: combinatorics, dfs and similar, divide and conquer, dp, probabilities, trees

Given a tree with $$$n$$$ nodes numbered from $$$1$$$ to $$$n$$$. Each node $$$i$$$ has an associated value $$$V_i$$$.

If the simple path from $$$u_1$$$ to $$$u_m$$$ consists of $$$m$$$ nodes namely $$$u_1 \rightarrow u_2 \rightarrow u_3 \rightarrow \dots u_{m-1} \rightarrow u_{m}$$$, then its alternating function $$$A(u_{1},u_{m})$$$ is defined as $$$A(u_{1},u_{m}) = \sum\limits_{i=1}^{m} (-1)^{i+1} \cdot V_{u_{i}}$$$. A path can also have $$$0$$$ edges, i.e. $$$u_{1}=u_{m}$$$.

Compute the sum of alternating functions of all unique simple paths. Note that the paths are directed: two paths are considered different if the starting vertices differ or the ending vertices differ. The answer may be large so compute it modulo $$$10^{9}+7$$$.

Input format:
The first line contains an integer $$$n$$$ $$$(2 \leq n \leq 2\cdot10^{5} )$$$ — the number of vertices in the tree.

The second line contains $$$n$$$ space-separated integers $$$V_1, V_2, \ldots, V_n$$$ ($$$-10^9\leq V_i \leq 10^9$$$) — values of the nodes.

The next $$$n-1$$$ lines each contain two space-separated integers $$$u$$$ and $$$v$$$ $$$(1\leq u, v\leq n, u \neq v)$$$ denoting an edge between vertices $$$u$$$ and $$$v$$$. It is guaranteed that the given graph is a tree.

Output format:
Print the total sum of alternating functions of all unique simple paths modulo $$$10^{9}+7$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Consider the first example.

A simple path from node $$$1$$$ to node $$$2$$$: $$$1 \rightarrow 2$$$ has alternating function equal to $$$A(1,2) = 1 \cdot (-4)+(-1) \cdot 1 = -5$$$.

A simple path from node $$$1$$$ to node $$$3$$$: $$$1 \rightarrow 3$$$ has alternating function equal to $$$A(1,3) = 1 \cdot (-4)+(-1) \cdot 5 = -9$$$.

A simple path from node $$$2$$$ to node $$$4$$$: $$$2 \rightarrow 1 \rightarrow 4$$$ has alternating function $$$A(2,4) = 1 \cdot (1)+(-1) \cdot (-4)+1 \cdot (-2) = 3$$$.

A simple path from node $$$1$$$ to node $$$1$$$ has a single node $$$1$$$, so $$$A(1,1) = 1 \cdot (-4) = -4$$$.

Similarly, $$$A(2, 1) = 5$$$, $$$A(3, 1) = 9$$$, $$$A(4, 2) = 3$$$, $$$A(1, 4) = -2$$$, $$$A(4, 1) = 2$$$, $$$A(2, 2) = 1$$$, $$$A(3, 3) = 5$$$, $$$A(4, 4) = -2$$$, $$$A(3, 4) = 7$$$, $$$A(4, 3) = 7$$$, $$$A(2, 3) = 10$$$, $$$A(3, 2) = 10$$$. So the answer is $$$(-5) + (-9) + 3 + (-4) + 5 + 9 + 3 + (-2) + 2 + 1 + 5 + (-2) + 7 + 7 + 10 + 10 = 40$$$.

Similarly $$$A(1,4)=-2, A(2,2)=1, A(2,1)=5, A(2,3)=10, A(3,3)=5, A(3,1)=9, A(3,2)=10, A(3,4)=7, A(4,4)=-2, A(4,1)=2, A(4,2)=3 , A(4,3)=7$$$ which sums upto 40.

Example input:
4
-4 1 5 -2
1 2
1 3
1 4

Example output:
40

Example input:
8
-2 6 -4 -4 -9 -3 -7 23
8 2
2 3
1 4
6 5
7 6
4 7
5 8

Example output:
4

Editorial:
An important observation for the question is
• $$$A(u,v) = -A(v,u) $$$ if there are even number of nodes on the simple path from $$$u$$$ to $$$v$$$
• $$$A(u,v) = A(v,u) $$$ if there are odd number of nodes on the simple path from $$$u$$$ to $$$v$$$
Hence $$$A(u,v) + A(v,u)=0 $$$ for paths with even number of nodes.
Hence the task has been reduced to finding the total sum of alternating function of paths with odd number of nodes. Also we can make use of the fact that $$$A(u,v) + A(v,u) = 2*A(u,v) $$$ , but this does not hold true when $$$u=v$$$, hence we must handle this case by subtracting $$$\sum\limits_{i=1}^{n} V_{i}$$$ from the final answer.
Now with the help of a single dfs we can calculate
• $$$odd_i$$$ the number of paths in the subtree of $$$i$$$ with odd number of nodes ending at node $$$i$$$.
• $$$even_i$$$ the number of paths in the subtree of $$$i$$$ with even number of nodes ending at node $$$i$$$.
In the first part of the solution, for each node $$$i$$$, we calculate its contribution to the alternating function for paths passing through this node but strictly lying within its subtree. For doing this we can merge two paths with either both having even or both having odd number of nodes ending at its children to create odd length paths.
For the case where both the paths have even number of nodes, the current node's contribution to the summation is $$$V_i$$$ because its position in the sequence of nodes is odd . Similarly, we add $$$-V_i$$$ for the other case. This can be done using a single dfs in $$$O(n)$$$ time as we have $$$odd_i$$$ and $$$even_i$$$ for all the nodes.
Now for the second part of the question, we have to consider the paths which end up outside the subtree. We have the information $$$odd_i$$$ and $$$even_i$$$ . We have to merge these paths with those ending at $$$parent_i$$$. How do we get this information?   Note that $$$odd_i$$$ and $$$even_i$$$ just represent paths strictly lying within the subtree of $$$i$$$ but not the entire tree. An important observation for this computation is -
If node $$$u$$$ has a total of $$$x$$$ odd and $$$y$$$ even length paths ending at it then, if $$$v$$$ is the neighbour of $$$u$$$ then $$$v$$$ has a total of $$$y$$$ odd and $$$x$$$ even length paths ending at it. It is fairly simple to observe. We know $$$odd_{root}$$$ and $$$even_{root}$$$ and since the subtree of $$$root$$$ is the entire tree, we can use these values for our requirement.   Now let's represent the total number of odd and even length paths ending at $$$i$$$ by $$$todd_i$$$ and $$$teven_i$$$ respectively. From our previous observation,
if $$$i$$$ is odd number of nodes away from the $$$root$$$ node -
• $$$todd_i = even_{root}$$$
• $$$teven_i = odd_{root}$$$
if $$$i$$$ is even number of nodes away from the $$$root$$$ node -
• $$$todd_i = odd_{root}$$$
• $$$teven_i = even_{root}$$$
The number of paths ending at $$$parent_i$$$ but lying strictly outside the subtree of $$$i$$$ can be calculated -
• odd length paths $$$= todd_{parent_i}-even_i$$$
• even length paths $$$= teven_{parent_i}-odd_i$$$
Now we have to construct odd-length paths by merging paths in the subtree of $$$i$$$ ending at node $$$i$$$ with paths ending at $$$parent_i$$$ but strictly lying outside the subtree of $$$i$$$. For paths with odd-length component ending at $$$i$$$ we must add $$$V_i$$$ to the summation and $$$-V_i$$$ otherwise.
Finally, the summation of contributions of each node yields you the total summation of alternating functions for all pair of nodes. This can be done for each node in $$$O(n)$$$ time.
The overall time complexity of the solution is $$$O(n)$$$.