← 返回题目列表

Codeforces · 1210/C

C. 卡米尔和制作直播

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

卡米尔喜欢观看竞技节目视频。他的 MeTube 频道最近订阅人数已达到 100 美元。为了庆祝这一点,他发布了一个视频,其中包含一个他尚未解决的有趣问题。你能帮助他吗?

给你一棵树 - 一个连接的无向图,由 $$$n$$$ 顶点组成,并通过 $$$n - 1$$$ 边连接。该树的根位于顶点$$$1$$$。如果顶点 $$$u$$$ 位于根和 $$$v$$$ 之间的最短路径上,则该顶点称为 $$$v$$$ 的祖先。特别是,顶点是其自身的祖先。

每个顶点 $$$v$$$ 都被分配了它的美度 $$$x_v$$$ — 一个不大于 $$$10^{12}$$$ 的非负整数。这使我们能够定义路径的美感。令 $$$u$$$ 为 $$$v$$$ 的祖先。然后我们将美感$$$f(u, v)$$$定义为$$$u$$$和$$$v$$$之间最短路径上所有顶点美感的最大公约数。形式上,如果 $$$u=t_1, t_2, t_3, \dots, t_k=v$$$ 是 $$$u$$$ 和 $$$v$$$ 之间最短路径上的顶点,则 $$$f(u, v) = \gcd(x_{t_1}, x_{t_2}, \dots, x_{t_k})$$$。这里,$$$\gcd$$$ 表示一组数字的最大公约数。特别是,$$$f(u, u) = \gcd(x_u) = x_u$$$。

你的任务是求总和

$$$$$$ \sum_{u\text{ 是 }v} f(u, v) 的祖先。 $$$$$$

由于结果可能太大,请以 $$$10^9 + 7$$$ 为模输出。

请注意,对于每个 $$$y$$$,$$$\gcd(0, y) = \gcd(y, 0) = y$$$。特别是,$$$\gcd(0, 0) = 0$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 100\,000$$$) — 树中的顶点数。

以下行包含 $$$n$$$ 整数 $$$x_1, x_2, \dots, x_n$$$ ($$$0 \le x_i \le 10^{12}$$$)。值$$$x_v$$$表示顶点$$$v$$$的美度。

以下 $$$n - 1$$$ 行描述了树的边缘。它们每个都包含两个整数 $$$a, b$$$ ($$$1 \le a, b \le n$$$, $$$a \neq b$$$) — 由单条边连接的顶点。

输出

输出所有路径 $$$(u, v)$$$ 上的美女总和,使得 $$$u$$$ 是 $$$v$$$ 的祖先。该总和应以 $$$10^9 + 7$$$ 为模打印。

示例

输入 #1

5
4 5 6 0 8
1 2
1 3
1 4
4 5

输出 #1

42

输入 #2

7
0 2 3 0 0 0 0
1 2
1 3
2 4
2 5
3 6
3 7

输出 #2

30

注意

下图显示了所有 $$$10$$$ 可能的路径,其中一个端点是另一端点的祖先。所有这些路径的美丽总和等于 $$$42$$$: