E. Знакопеременное дерево
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано дерево с $$$n$$$ вершинами, пронумерованными с $$$1$$$ до $$$n$$$. В вершине $$$i$$$ записано значение $$$V_i$$$.

Если простой путь от вершины $$$u_1$$$ до вершины $$$u_m$$$ состоит из $$$m$$$ вершин, а именно из $$$u_1 \rightarrow u_2 \rightarrow u_3 \rightarrow \dots 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}}$$$. Путь может содержать $$$0$$$ рёбер, т. е. $$$u_{1}=u_{m}$$$.

Вычислите сумму знакопеременных сумм для всех различных простых путей в дереве. Обратите внимание, пути ориентированны: два пути считаются различными, если у них различное начало или различный конец. Так как ответ может быть большим, выведите остаток от деления его на $$$10^{9}+7$$$.

Входные данные

В первой строке содержится целое число $$$n$$$ $$$(2 \leq n \leq 2\cdot10^{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$$$.

Примеры
Входные данные
4
-4 1 5 -2
1 2
1 3
1 4
Выходные данные
40
Входные данные
8
-2 6 -4 -4 -9 -3 -7 23
8 2
2 3
1 4
6 5
7 6
4 7
5 8
Выходные данные
4
Примечание

Рассмотрим первый пример.

Знакопеременная сумма для простого пути из вершины $$$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$$$.