#P18643. Forestry
Forestry
Forestry
题目描述
给定一棵包含 个顶点、 条边的树 。顶点编号为 ,边编号为 。第 条边连接顶点 和 。顶点 上写有整数 。
共有 种选择树中若干条边的方式,包括不选任何边和选中全部边。
对于每一种选边方式,进行以下操作:
- 从 中删除所有未被选中的边,得到图 。
- 对 的每个连通块,取该块所有顶点上整数的最小值。
- 将这些最小值相加,作为这次选边方式的得分。
请计算所有选边方式的得分总和,答案对 取模。
输入格式
N
A_1 A_2 ... A_N
U_1 V_1
U_2 V_2
...
U_{N-1} V_{N-1}
输入仅包含一组数据,所有数均为整数。
输出格式
输出一个整数,表示所有选边方式的得分总和对 取模的结果。
数据范围
- 。
- 。
- 。
- 输入给出的无向图是一棵树。
样例输入 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