{"problem":{"name":"E. Alternating Tree","description":{"content":"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","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF960E"},"statements":[{"statement_type":"Markdown","content":"Given a tree with $n$ nodes numbered from $1$ to $n$. Each node $i$ has an associated value $V_i$.\n\nIf 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}$.\n\nCompute 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$.\n\n## Input\n\nThe first line contains an integer $n$ $(2 \\leq n \\leq 2\\cdot10^{5} )$ — the number of vertices in the tree.\n\nThe 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.\n\nThe 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.\n\n## Output\n\nPrint the total sum of alternating functions of all unique simple paths modulo $10^{9}+7$.\n\n[samples]\n\n## Note\n\nConsider the first example.\n\nA 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$.\n\nA 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$.\n\nA 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$.\n\nA simple path from node $1$ to node $1$ has a single node $1$, so $A(1,1) = 1 \\cdot (-4) = -4$.\n\nSimilarly, $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$.\n\nSimilarly $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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"给定一棵包含 $n$ 个节点的树，节点编号为 $1$ 到 $n$。每个节点 $i$ 有一个关联值 $V_i$。\n\n如果从 $u_1$ 到 $u_m$ 的简单路径包含 $m$ 个节点，即 $u_1 \\to u_2 \\to u_3 \\to \\dots \\to u_{m-1} \\to u_m$，则其交错和 $A(u_1, u_m)$ 定义为 $A(u_1, u_m) = \\sum_{i=1}^m (-1)^{i+1} \\cdot V_{u_i}$。路径也可以包含 $0$ 条边，即 $u_1 = u_m$。\n\n计算所有唯一简单路径的交错和之和。注意路径是有向的：如果起点不同或终点不同，则两条路径被视为不同。答案可能很大，因此请对 $10^9 + 7$ 取模。\n\n第一行包含一个整数 $n$ $(2 \\leq n \\leq 2 \\cdot 10^5)$ —— 树中顶点的数量。\n\n第二行包含 $n$ 个用空格分隔的整数 $V_1, V_2, \\dots, V_n$ ($-10^9 \\leq V_i \\leq 10^9$) —— 节点的值。\n\n接下来的 $n - 1$ 行每行包含两个用空格分隔的整数 $u$ 和 $v$ $(1 \\leq u, v \\leq n, u \\neq v)$，表示节点 $u$ 和 $v$ 之间有一条边。保证给定的图是一棵树。\n\n请输出所有唯一简单路径的交错和之和对 $10^9 + 7$ 取模的结果。\n\n考虑第一个例子。\n\n从节点 $1$ 到节点 $2$ 的简单路径：$1 \\to 2$ 的交错和为 $A(1, 2) = 1 \\cdot (-4) + (-1) \\cdot 1 = -5$。\n\n从节点 $1$ 到节点 $3$ 的简单路径：$1 \\to 3$ 的交错和为 $A(1, 3) = 1 \\cdot (-4) + (-1) \\cdot 5 = -9$。\n\n从节点 $2$ 到节点 $4$ 的简单路径：$2 \\to 1 \\to 4$ 的交错和为 $A(2, 4) = 1 \\cdot (1) + (-1) \\cdot (-4) + 1 \\cdot (-2) = 3$。\n\n从节点 $1$ 到节点 $1$ 的路径只有一个节点 $1$，因此 $A(1, 1) = 1 \\cdot (-4) = -4$。\n\n类似地，$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$。\n\n类似地，$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。\n\n## Input\n\n第一行包含一个整数 $n$ $(2 \\leq n \\leq 2 \\cdot 10^5)$ —— 树中顶点的数量。第二行包含 $n$ 个用空格分隔的整数 $V_1, V_2, \\dots, 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$ 之间有一条边。保证给定的图是一棵树。\n\n## Output\n\n请输出所有唯一简单路径的交错和之和对 $10^9 + 7$ 取模的结果。\n\n[samples]\n\n## Note\n\n考虑第一个例子。从节点 $1$ 到节点 $2$ 的简单路径：$1 \\to 2$ 的交错和为 $A(1, 2) = 1 \\cdot (-4) + (-1) \\cdot 1 = -5$。从节点 $1$ 到节点 $3$ 的简单路径：$1 \\to 3$ 的交错和为 $A(1, 3) = 1 \\cdot (-4) + (-1) \\cdot 5 = -9$。从节点 $2$ 到节点 $4$ 的简单路径：$2 \\to 1 \\to 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。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of nodes in a tree.  \nLet $ V = (V_1, V_2, \\dots, V_n) \\in \\mathbb{Z}^n $ be the vector of node values.  \nLet $ T = (V, E) $ be a tree with node set $ \\{1, 2, \\dots, n\\} $ and edge set $ E $ of size $ n-1 $.  \n\nFor any ordered pair of nodes $ (u, v) $, let $ P(u, v) = (u = u_1, u_2, \\dots, u_m = v) $ denote the unique simple path from $ u $ to $ v $, where $ m \\geq 1 $ is the number of nodes in the path.  \n\nDefine the **alternating function** of path $ P(u, v) $ as:  \n$$\nA(u, v) = \\sum_{i=1}^{m} (-1)^{i+1} V_{u_i}\n$$\n\n**Constraints**  \n1. $ 2 \\leq n \\leq 2 \\cdot 10^5 $  \n2. $ -10^9 \\leq V_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. The graph is a tree (connected, acyclic, undirected).  \n\n**Objective**  \nCompute:  \n$$\n\\sum_{u=1}^{n} \\sum_{v=1}^{n} A(u, v) \\mod (10^9 + 7)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF960E","tags":["combinatorics","dfs and similar","divide and conquer","dp","probabilities","trees"],"sample_group":[["4\n-4 1 5 -2\n1 2\n1 3\n1 4","40"],["8\n-2 6 -4 -4 -9 -3 -7 23\n8 2\n2 3\n1 4\n6 5\n7 6\n4 7\n5 8","4"]],"created_at":"2026-03-03 11:00:39"}}