读写要求

本题采用文件读写，请在提交代码时使用正确的文件名，否则会导致 RE。

输入文件：gcd.in

输出文件：gcd.out

题目描述

给定一棵由 $n$ 个节点和 $n-1$ 条边组成的连通无向树，以节点 $1$ 为根。如果一个节点 $u$ 位于根到 $v$ 的最短路径上，则称 $u$ 是 $v$ 的祖先。特别地，一个节点是自己的祖先。

每个节点 $v$ 被赋予一个美丽值 $x_v$——一个不超过 $10^{12}$ 的非负整数。

设 $u$ 是 $v$ 的祖先。定义路径美丽值 $f(u,v)$ 为从 $u$ 到 $v$ 最短路径上所有节点美丽值的最大公约数。即，若 $u=t_1,t_2,t_3,\dots,t_k=v$ 是该路径上的节点，则 $f(u,v)=\gcd(x_{t_1},x_{t_2},\dots,x_{t_k})$。特别地，$f(u,u)=\gcd(x_u)=x_u$。

你的任务是求：

由于结果可能过大，请对 $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}$)，表示每个节点的美丽值。

接下来 $n-1$ 行，每行两个整数 $a,b$ ($1\le a,b\le n$, $a\neq b$)，表示一条边。

输出格式

输出所有祖先-后代路径美丽值的和，对 $10^9+7$ 取模。

样例输入 #1

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

样例输出 #1

42

样例解释

下图展示了所有 $10$ 条一端为另一端祖先的路径，这些路径的美丽值之和为 $42$：

样例输入 #2

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

样例输出 #2

30

数据范围

• $2\le n\le 100\,000$
• $0\le x_i\le 10^{12}$

知识点与难度