Kamil and Making a Stream
Contest: Dasha Code Championship - SPb Finals Round (only for onsite-finalists)
Difficulty rating: 2000
Tags: math, number theory, trees

Kamil likes streaming the competitive programming videos. His MeTube channel has recently reached $$$100$$$ million subscribers. In order to celebrate this, he posted a video with an interesting problem he couldn't solve yet. Can you help him?

You're given a tree — a connected undirected graph consisting of $$$n$$$ vertices connected by $$$n - 1$$$ edges. The tree is rooted at vertex $$$1$$$. A vertex $$$u$$$ is called an ancestor of $$$v$$$ if it lies on the shortest path between the root and $$$v$$$. In particular, a vertex is an ancestor of itself.

Each vertex $$$v$$$ is assigned its beauty $$$x_v$$$ — a non-negative integer not larger than $$$10^{12}$$$. This allows us to define the beauty of a path. Let $$$u$$$ be an ancestor of $$$v$$$. Then we define the beauty $$$f(u, v)$$$ as the greatest common divisor of the beauties of all vertices on the shortest path between $$$u$$$ and $$$v$$$. Formally, if $$$u=t_1, t_2, t_3, \dots, t_k=v$$$ are the vertices on the shortest path between $$$u$$$ and $$$v$$$, then $$$f(u, v) = \gcd(x_{t_1}, x_{t_2}, \dots, x_{t_k})$$$. Here, $$$\gcd$$$ denotes the greatest common divisor of a set of numbers. In particular, $$$f(u, u) = \gcd(x_u) = x_u$$$.

Your task is to find the sum

$$$$$$ \sum_{u\text{ is an ancestor of }v} f(u, v). $$$$$$

As the result might be too large, please output it modulo $$$10^9 + 7$$$.

Note that for each $$$y$$$, $$$\gcd(0, y) = \gcd(y, 0) = y$$$. In particular, $$$\gcd(0, 0) = 0$$$.

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 100\,000$$$) — the number of vertices in the tree.

The following line contains $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$0 \le x_i \le 10^{12}$$$). The value $$$x_v$$$ denotes the beauty of vertex $$$v$$$.

The following $$$n - 1$$$ lines describe the edges of the tree. Each of them contains two integers $$$a, b$$$ ($$$1 \le a, b \le n$$$, $$$a \neq b$$$) — the vertices connected by a single edge.

Output format:
Output the sum of the beauties on all paths $$$(u, v)$$$ such that $$$u$$$ is ancestor of $$$v$$$. This sum should be printed modulo $$$10^9 + 7$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 768.0 MB

Note:
The following figure shows all $$$10$$$ possible paths for which one endpoint is an ancestor of another endpoint. The sum of beauties of all these paths is equal to $$$42$$$:

Example input:
5
4 5 6 0 8
1 2
1 3
1 4
4 5

Example output:
42

Example input:
7
0 2 3 0 0 0 0
1 2
1 3
2 4
2 5
3 6
3 7

Example output:
30

Editorial:
Let's prove the following observation:
Fix a vertex $$$v$$$ (the bottom end of the path), and consider all its ancestors $$$u$$$. The number of distinct values of $$$f(u,v)$$$ is at most $$$\log_2(10^{12})$$$.
To prove this observation, consider the ancestors of $$$v$$$ in the order from the bottom-most to top-most: $$$v=u_0, u_1, u_2, u_3, \dots, u_k=1$$$. Notice that $$$f(u_i, v) = \gcd(x_{u_0}, x_{u_1}, x_{u_2}, \dots, x_{u_i})$$$. Therefore, each consecutive $$$u_i$$$ adds another value $$$x_{u, i}$$$ to the gcd of all numbers. If a gcd of all numbers changes, it must be a divisor of the previous gcd. Therefore, it's easy to see that it can change at most $$$\log_2(10^{12})$$$ times.
We can now implement a depth-first search. If we invoke a recursive call in vertex $$$v$$$, we will receive the multiset of values $$$\{f(u, v) \mid u\text{ is an ancestor of }v\}$$$. We add all these values to the result and run the recursive calls in the children.
This is currently $$$O(n^2)$$$ or $$$O(n^2\log n)$$$, but we can improve it by actually using a map from the distinct values in the multiset to the number of their occurrences. Then each map will have no more than $$$O\log_2(10^{12})$$$ elements. As we need to compute $$$\gcd$$$'s throughout the algorithm, this solution allows us to solve the problem in $$$O(n\log^2(10^{12}))$$$ time and in $$$O(n \log(10^{12}))$$$ memory.
It's also possible to solve the problem using jump-pointers. Each jump-pointer will additionally hold the greatest common divisor of all the numbers we jump over when following the pointer.