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


-----Examples-----
Input
5
4 5 6 0 8
1 2
1 3
1 4
4 5

Output
42

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

Output
30



-----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$: [Image]

Source: codeforces | Difficulty: HARD
Tags: Number theory

Tree algorithms

Mathematics


Solutions:
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))
main()


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)
main()


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()


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)
main()


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()


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)