CF348B Apple Tree

给定一棵有 $n$ 个结点的有根树，每个叶子结点上有一个整数——表示该结点上的苹果数量。 一棵子树的权值是该子树所有叶子结点上的数字之和。例如，对应于某个叶子结点的子树，其权值就是写在该叶子上的数字。 如果对于树中的每个结点 $v$，由 $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 格式。

由 ChatGPT 5 翻译