Kamil and Making a Stream (Codeforces 1210C)
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 collections import Counter

def gcd(x, y):
    while y != 0:
        (x, y) = (y, x % y)
    return x

def main():
    n = int(input())
    arr = readIntArr()
    adj = [[] for _ in range(n)]
    for _ in range(n - 1):
        (u, v) = readIntArr()
        u -= 1
        v -= 1
        adj[u].append(v)
        adj[v].append(u)
    ans = 0
    visited = [False] * n
    visited[0] = True
    stack = [[0, Counter()]]
    while stack:
        (node, parentGCDs) = stack.pop()
        newGCDs = Counter()
        ans += arr[node]
        ans %= MOD
        newGCDs[arr[node]] += 1
        for (k, v) in parentGCDs.items():
            g = gcd(arr[node], k)
            ans += g * v % MOD
            ans %= MOD
            newGCDs[g] += v
        for nex in adj[node]:
            if visited[nex] == False:
                visited[nex] = True
                stack.append([nex, newGCDs])
    print(ans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(i, j):
    print('? {} {}'.format(i, j))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(' '.join([str(x) for x in ans])))
    sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
    main()

Solution (Python):
from collections import Counter
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

def gcd(x, y):
    while y != 0:
        (x, y) = (y, x % y)
    return x

def main():
    n = int(input())
    arr = readIntArr()
    adj = [[] for _ in range(n)]
    for _ in range(n - 1):
        (u, v) = readIntArr()
        u -= 1
        v -= 1
        adj[u].append(v)
        adj[v].append(u)

    @bootstrap
    def dfs(node, p, parentGCDs):
        newGCDs = Counter()
        newGCDs[arr[node]] += 1
        ans[0] += arr[node]
        ans[0] %= MOD
        for (k, v) in parentGCDs.items():
            newG = gcd(arr[node], k)
            ans[0] += newG * v % MOD
            ans[0] %= MOD
            newGCDs[newG] += v
        for nex in adj[node]:
            if nex != p:
                yield dfs(nex, node, newGCDs)
        yield None
    ans = [0]
    parentGCDs = Counter()
    dfs(0, -1, parentGCDs)
    print(ans[0])
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(i, j):
    print('? {} {}'.format(i, j))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(' '.join([str(x) for x in ans])))
    sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
    main()

Solution (Python):
n = int(input())
beauty = list(map(int, input().strip().split()))
tree = [[] for i in range(n)]
mod = 1000000007
used = [False for i in range(n)]

def gcd(a, b):
    mn = min(a, b)
    mx = max(a, b)
    if mn == 0:
        return mx
    md = mx % mn
    if md == 0:
        return mn
    else:
        return gcd(mn, md)
for i in range(n - 1):
    (a, b) = map(int, input().strip().split())
    tree[a - 1].append(b - 1)
    tree[b - 1].append(a - 1)
segment_vals = [{} for i in range(n)]
ans = beauty[0]
segment_vals[0][beauty[0]] = 1
cur_nodes = [0]
used[0] = True
while 1:
    new_nodes = []
    for node in cur_nodes:
        for potential_new in tree[node]:
            if used[potential_new] == False:
                used[potential_new] = True
                new_nodes.append(potential_new)
                new_beauty = beauty[potential_new]
                segment_vals[potential_new][new_beauty] = 1
                for g in segment_vals[node].keys():
                    segment_gcd = gcd(new_beauty, g)
                    segment_vals[potential_new][segment_gcd] = segment_vals[potential_new].get(segment_gcd, 0) + segment_vals[node][g]
                for k in segment_vals[potential_new].keys():
                    ans += k * segment_vals[potential_new][k]
                    ans = ans % mod
    if len(new_nodes) == 0:
        break
    else:
        cur_nodes = new_nodes
print(ans)