Kamil and Making a Stream (Codeforces 1230E)
Tags: Math, 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: 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: 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$$$.

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$$$:  

Sample Inputs:
5
4 5 6 0 8
1 2
1 3
1 4
4 5

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

Sample Outputs:
42

30

Solution (Python):
from math import gcd
from collections import deque
from bisect import bisect_left
from sys import setrecursionlimit
MOD = 1000000007

def modInt(mod):

    class ModInt:

        def __init__(self, value):
            self.value = value % mod

        def __int__(self):
            return self.value

        def __eq__(self, other):
            return self.value == other.value

        def __hash__(self):
            return hash(self.value)

        def __add__(self, other):
            return ModInt(self.value + int(other))

        def __sub__(self, other):
            return ModInt(self.value - int(other))

        def __mul__(self, other):
            return ModInt(self.value * int(other))

        def __floordiv__(self, other):
            return ModInt(self.value // int(other))

        def __truediv__(self, other):
            return ModInt(self.value * pow(int(other), mod - 2, mod))
    return ModInt
ModInt = modInt(MOD)

def main():
    n = int(input())
    setrecursionlimit(n + 100)
    xx = [0] + [int(x) for x in input().split()]
    edges = []
    neighbors = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        (v1, v2) = [int(x) for x in input().split()]
        neighbors[v1].append(v2)
        neighbors[v2].append(v1)
    visited = [False] * (n + 1)
    dq = deque()
    dq.append((1, []))
    sum = ModInt(0)
    while dq:
        (u, gcds) = dq.popleft()
        gcdns = [[xx[u], 1]]
        sum = sum + xx[u]
        for (g, c) in gcds:
            gcdn = gcd(xx[u], g)
            sum = sum + gcdn * c
            if gcdn == gcdns[-1][0]:
                gcdns[-1][1] += c
            else:
                gcdns.append([gcdn, c])
        visited[u] = True
        for v in neighbors[u]:
            if not visited[v]:
                dq.append((v, gcdns))
    print(int(sum))
if __name__ == '__main__':
    main()

Solution (Python):
from math import gcd
from collections import deque
from bisect import bisect_left
from sys import setrecursionlimit
MOD = 1000000007

def main():
    n = int(input())
    setrecursionlimit(n + 100)
    xx = [0] + [int(x) for x in input().split()]
    edges = []
    neighbors = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        (v1, v2) = [int(x) for x in input().split()]
        neighbors[v1].append(v2)
        neighbors[v2].append(v1)
    visited = [False] * (n + 1)
    dq = deque()
    dq.append((1, []))
    sum = 0
    while dq:
        (u, gcds) = dq.popleft()
        gcdns = [[xx[u], 1]]
        sum = (sum + xx[u]) % MOD
        for (g, c) in gcds:
            gcdn = gcd(xx[u], g)
            sum = (sum + gcdn * c) % MOD
            if gcdn == gcdns[-1][0]:
                gcdns[-1][1] += c
            else:
                gcdns.append([gcdn, c])
        visited[u] = True
        for v in neighbors[u]:
            if not visited[v]:
                dq.append((v, gcdns))
    print(sum)
if __name__ == '__main__':
    main()

Solution (Python):
from math import gcd
from collections import deque
from bisect import bisect_left
from sys import setrecursionlimit
MOD = 1000000007

def main():
    n = int(input())
    setrecursionlimit(n + 100)
    xx = [0] + [int(x) for x in input().split()]
    edges = []
    for _ in range(n - 1):
        edge = [int(x) for x in input().split()]
        edges.append(edge)
        edges.append(list(reversed(edge)))
    edges.sort()
    visited = [False] * (n + 1)
    dq = deque()
    dq.append((1, []))
    sum = 0
    while dq:
        (u, gcds) = dq.popleft()
        gcdns = [[xx[u], 1]]
        sum = (sum + xx[u]) % MOD
        for (g, c) in gcds:
            gcdn = gcd(xx[u], g)
            sum = (sum + gcdn * c) % MOD
            if gcdn == gcdns[-1][0]:
                gcdns[-1][1] += c
            else:
                gcdns.append([gcdn, c])
        visited[u] = True
        i = bisect_left(edges, [u, 0])
        if i == 2 * (n - 1):
            continue
        (w, v) = edges[i]
        while w == u and i < 2 * (n - 1):
            if not visited[v]:
                dq.append((v, gcdns))
            i += 1
            if i < 2 * (n - 1):
                (w, v) = edges[i]
    print(sum)
if __name__ == '__main__':
    main()