给你一棵有 n 个顶点的有根树。每个叶顶点都有一个整数——该顶点中苹果的数量。
子树的权重是该子树叶子中所有数字的总和。例如,某个叶子对应的子树的权重就是叶子中写入的数字。
如果对于树的每个顶点 v,其与顶点 v 的子节点相对应的所有子树都具有相同的权重,则该树是平衡的。
计算为了使树保持平衡而需要从树上(特别是从它的一些叶子上)移除的苹果的最小数量。请注意,您总是可以通过移除所有苹果来实现目标。
输入
第一行包含整数 n (2 ≤ n ≤ 105),显示树中的顶点数。下一行包含n个整数a1,a2,...,an(0≤ai≤108),ai是顶点号i中苹果的数量。非叶子顶点中的苹果数量保证为零。
然后遵循 n - 1 行,描述树的边缘。每行包含一对整数 xi, yi (1 ≤ xi, yi ≤ n, xi ≠ yi) — 由边连接的顶点。
顶点索引从 1 到 n。顶点 1 是根。
输出
打印一个整数——为了使树保持平衡而需要移除的最小苹果数量。
请不要编写 %lld 说明符来读取或写入 С++ 中的 64 位整数。最好使用 sin、cout 流 cin、cout 或 %I64d 说明符。
示例
输入 #1
6 0 0 12 13 5 6 1 2 1 3 1 4 2 5 2 6
输出 #1
6