← 返回题目列表

Codeforces · 348/B

B. 苹果树

中文机器翻译题面 查看原题

给你一棵有 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