CF348B Apple Tree

给定一棵包含 $n$ 个节点的有根树。每个叶节点上有一个整数，表示该节点上的苹果数量。 子树的**权重**定义为该子树中所有叶节点上数字的总和。例如，对应某个叶节点的子树的权重就是该叶节点上写的数字。 如果对于树中的每个节点 $v$，其所有子节点对应的子树都具有相同的权重，则称这棵树是**平衡的**。 请计算为了使树变得平衡，需要从树中（具体来说是从某些叶节点上）移除的最少苹果数量。注意：总是可以通过移除所有苹果来达到目标。

第一行包含一个整数 $n$ $(2 \le n \le 10^5)$，表示树的结点数。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(0 \le a_i \le 10^8)$，$a_i$ 表示编号为 $i$ 的结点的苹果数。保证非叶子结点上的苹果数为 $0$。 接下来 $n-1$ 行，每行描述一条树的边。每行包含两个整数 $x_i, y_i$ $(1 \le x_i, y_i \le n, \; x_i \ne y_i)$，表示 $x_i$ 和 $y_i$ 之间有一条边。 结点编号从 $1$ 到 $n$。结点 $1$ 是树根。

输出一个整数，表示最少需要拿掉的苹果数，使得该树平衡。

请不要在 C++ 代码中使用 `%lld` 读取或输出 $64$ 位整数。推荐使用 `cin, cout` 流或 `%I64d` 格式。