2593: 统计损失
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：7
解决：3
题目描述
SJY有一天被LLT紧急召去计算一些可能的损失。LLT元首管理的SHB国的交通形成了一棵树，现在将会出现一颗陨石砸在SHB国中，并且陨石砸毁的必定是SHB国构成的交通树上的一条路径。SHB国的损失可表示为被砸毁的路径上的所有城市价值之积。现在还暂时无法确定陨石的掉落路线，所以LLT元首希望SJY能够告诉他SHB国在受到每一种砸毁方式后会受到的损失之和模10086之后的值。注意：单独一个节点也被认为是合法的路径。
输入
第1行一个数n，表示城市数。
第2行n个数，第i个数表示第i个城市的价值。
第3到n+1行，每行两个数u,v，表示城市u,v之间有一条道路。
输出
包含一个数，表示SHB国将受到的损失之和。
样例输入 复制
5
7 6 6 1 1
1 2
2 3
2 4
1 5
样例输出 复制
778提示
【数据规模和约定】 对于20%的数据，n<=100; 对于50%的数据，n<=3000; 对于100%的数据，n<=100000。