Kamil and Making a Stream (Codeforces 1229B)
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):
import sys

def gcd(a, b):
    if a > b:
        (a, b) = (b, a)
    while a != 0:
        b = b - a * (b // a)
        (a, b) = (b, a)
    return b
q = 10 ** 9 + 7
n = int(sys.stdin.readline().strip())
x = list(map(int, sys.stdin.readline().strip().split()))
p = [-1] * n
e = [[] for i in range(0, n)]
for i in range(0, n - 1):
    (u, v) = list(map(int, sys.stdin.readline().strip().split()))
    e[u - 1].append(v - 1)
    e[v - 1].append(u - 1)
v = [0]
B = [[] for i in range(0, n)]
B[0] = [x[0]]
F = [[] for i in range(0, n)]
F[0] = [1]
ans = x[0]
while len(v) != 0:
    if len(e[v[-1]]) == 0:
        z = v.pop()
    else:
        w = v[-1]
        u = e[w].pop()
        if u != p[w]:
            v.append(u)
            p[u] = w
            b = len(B[w])
            for i in range(0, b):
                B[u].append(gcd(B[w][i], x[u]))
                F[u].append(F[w][i])
                bu = len(B[u])
                if bu >= 2:
                    if B[u][bu - 1] == B[u][bu - 2]:
                        z = B[u].pop()
                        F[u][bu - 2] = F[u][bu - 2] + F[u][bu - 1]
                        z = F[u].pop()
            B[u].append(x[u])
            F[u].append(1)
            bu = len(B[u])
            if bu >= 2:
                if B[u][bu - 1] == B[u][bu - 2]:
                    z = B[u].pop()
                    F[u][bu - 2] = F[u][bu - 2] + F[u][bu - 1]
                    z = F[u].pop()
            bu = len(B[u])
            for i in range(0, bu):
                ans = ans + B[u][i] * F[u][i] % q
print(ans % q)

Solution (Python):
from __future__ import division, print_function
from collections import deque

def main():

    def gcd(a, b):
        if a < b:
            (a, b) = (b, a)
        while b:
            (a, b) = (b, a % b)
        return a
    n = int(input())
    val = list(map(int, input().split()))
    gcds = [{} for _ in range(n)]
    edges = [[] for _ in range(n + 1)]
    for i in range(n - 1):
        (u, v) = map(int, input().split())
        edges[u].append(v)
        edges[v].append(u)
    visited = [0] * n
    q = deque()
    q.append(1)
    visited[0] = 1
    mod = 10 ** 9 + 7
    result = 0
    while q:
        u = q.popleft()
        x = val[u - 1]
        if x not in gcds[u - 1]:
            gcds[u - 1][x] = 1
        else:
            gcds[u - 1][x] += 1
        for k in gcds[u - 1]:
            result = (result + gcds[u - 1][k] * k) % mod
        for v in edges[u]:
            if visited[v - 1] == 0:
                temp = val[v - 1]
                for item in gcds[u - 1]:
                    a = gcd(item, temp)
                    if a not in gcds[v - 1]:
                        gcds[v - 1][a] = gcds[u - 1][item]
                    else:
                        gcds[v - 1][a] += gcds[u - 1][item]
                visited[v - 1] = 1
                q.append(v)
    print(result)
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
import os, sys
from io import IOBase, BytesIO
BUFSIZE = 8192

class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = 'x' in file.mode or 'w' in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill():
            pass
        return super(FastIO, self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill()
            self.newlines = s.count(b'\n') + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            (self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s: self.buffer.write(s.encode('ascii'))
            self.read = lambda : self.buffer.read().decode('ascii')
            self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import sys

class ostream:

    def __lshift__(self, a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'

def readnumbers(zero=0):
    conv = ord if py2 else lambda x: x
    A = []
    numb = zero
    sign = 1
    i = 0
    s = sys.stdin.buffer.read()
    try:
        while True:
            if s[i] >= b'0'[0]:
                numb = 10 * numb + conv(s[i]) - 48
            elif s[i] == b'-'[0]:
                sign = -1
            elif s[i] != b'\r'[0]:
                A.append(sign * numb)
                numb = zero
                sign = 1
            i += 1
    except:
        pass
    if s and s[-1] >= b'0'[0]:
        A.append(sign * numb)
    return A
if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

def gcd(a, b):
    while b:
        (a, b) = (b, a % b)
    return abs(a)
MOD = 10 ** 9 + 7
N = int(input())
B = [int(a) for a in input().split()]
X = [[] for i in range(N)]
for i in range(N - 1):
    (x, y) = map(int, input().split())
    X[x - 1].append(y - 1)
    X[y - 1].append(x - 1)
P = [-1] * N
Q = deque([0])
R = []
while Q:
    i = deque.popleft(Q)
    R.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            deque.append(Q, a)
A = [{} for _ in range(N)]
ans = 0
for r in R:
    ans += B[r]
    A[r][B[r]] = 1
    if r == 0:
        continue
    p = P[r]
    for a in A[p]:
        g = gcd(a, B[r])
        ans += g * A[p][a]
        if g in A[r]:
            A[r][g] += A[p][a]
        else:
            A[r][g] = A[p][a]
    ans %= MOD
print(ans)