CF960E Alternating Tree

给定一棵有 $n$ 个节点的树，节点编号从 $1$ 到 $n$。每个节点 $i$ 有一个关联值 $V_i$。 如果从 $u_1$ 到 $u_m$ 的简单路径包含 $m$ 个节点，记为 $u_1 \rightarrow u_2 \rightarrow u_3 \rightarrow \dots \rightarrow u_{m-1} \rightarrow u_m$，则其交错函数 $A(u_1, u_m)$ 定义为 $A(u_1, u_m) = \sum\limits_{i=1}^{m} (-1)^{i+1} \cdot V_{u_i}$。一条路径也可以没有边，即 $u_1 = u_m$。 请计算所有唯一简单路径的交错函数之和。注意，路径是有向的：如果起点或终点不同，则认为是不同的路径。答案可能很大，请对 $10^9+7$ 取模。

第一行包含一个整数 $n$ $(2 \leq n \leq 2 \cdot 10^5)$，表示树的节点数。 第二行包含 $n$ 个用空格分隔的整数 $V_1, V_2, \ldots, V_n$，表示每个节点的值，$-10^9 \leq V_i \leq 10^9$。 接下来的 $n-1$ 行，每行包含两个用空格分隔的整数 $u$ 和 $v$ $(1 \leq u, v \leq n, u \neq v)$，表示节点 $u$ 和节点 $v$ 之间有一条边。保证给定的图是一棵树。

输出所有唯一简单路径的交错函数之和，对 $10^9+7$ 取模。

以第一个样例为例： 从节点 $1$ 到节点 $2$ 的简单路径：$1 \rightarrow 2$，其交错函数为 $A(1,2) = 1 \cdot (-4) + (-1) \cdot 1 = -5$。 从节点 $1$ 到节点 $3$ 的简单路径：$1 \rightarrow 3$，其交错函数为 $A(1,3) = 1 \cdot (-4) + (-1) \cdot 5 = -9$。 从节点 $2$ 到节点 $4$ 的简单路径：$2 \rightarrow 1 \rightarrow 4$，其交错函数为 $A(2,4) = 1 \cdot 1 + (-1) \cdot (-4) + 1 \cdot (-2) = 3$。 从节点 $1$ 到节点 $1$ 的路径只有一个节点 $1$，所以 $A(1,1) = 1 \cdot (-4) = -4$。 同理，$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$。所以答案为 $(-5) + (-9) + 3 + (-4) + 5 + 9 + 3 + (-2) + 2 + 1 + 5 + (-2) + 7 + 7 + 10 + 10 = 40$。 同理，$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$，总和为 $40$。 由 ChatGPT 4.1 翻译