#P18643. Forestry

Forestry

Forestry

题目描述

给定一棵包含 NN 个顶点、N−1N-1 条边的树 TT。顶点编号为 1,2,…,N1,2,\ldots,N,边编号为 1,2,…,N−11,2,\ldots,N-1。第 ii 条边连接顶点 UiU_i 和 ViV_i。顶点 vv 上写有整数 AvA_v。

共有 2N−12^{N-1} 种选择树中若干条边的方式,包括不选任何边和选中全部边。

对于每一种选边方式,进行以下操作:

  1. 从 TT 中删除所有未被选中的边,得到图 GG。
  2. 对 GG 的每个连通块,取该块所有顶点上整数的最小值。
  3. 将这些最小值相加,作为这次选边方式的得分。

请计算所有选边方式的得分总和,答案对 998244353998244353 取模。

输入格式

N
A_1 A_2 ... A_N
U_1 V_1
U_2 V_2
...
U_{N-1} V_{N-1}

输入仅包含一组数据,所有数均为整数。

输出格式

输出一个整数,表示所有选边方式的得分总和对 998244353998244353 取模的结果。

数据范围

  • 2≤N≤3×1052\le N\le3\times10^5。
  • 1≤Ai≤1091\le A_i\le10^9。
  • 1≤Ui,Vi≤N1\le U_i,V_i\le N。
  • 输入给出的无向图是一棵树。

样例输入 1

4
1 2 3 4
1 2
2 4
3 2

样例输出 1

44

样例输入 2

5
3 5 6 5 1
4 1
2 3
3 5
1 3

样例输出 2

154