There is a rooted tree of N vertices rooted at vertex 1. Each vertex v has a value A_{v} associated with it.

You choose a vertex v (possibly the root) from the tree and remove all vertices on the path from the root to the vertex v, also including v. This will result in a forest of zero or more connected components.

The beauty of a connected component is the \mathrm{GCD} of the values of all vertices in the component. Find the maximum value of the sum of beauties of the obtained connected components for any choice of v.

Here, \mathrm{GCD} stands for [Greatest Common Divisor].

------ Input Format ------ 

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N — the size of the tree.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the values associated with each vertex.
- The next N-1 lines contain two space-separated integers u and v — denoting an undirected edge between nodes u and v.

It is guaranteed that the edges given in the input form a tree.

------ Output Format ------ 

For each test case output the maximum value of the sum of beauties of the obtained connected components for any choice of v.

------ Constraints ------ 

$1 ≤ T ≤ 2\cdot10^{4}$
$1 ≤ N ≤ 3\cdot10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
$1 ≤ u,v ≤ N$ and $u \neq v$
- It is guaranteed that the edges given in the input form a tree.
- The sum of $N$ over all test cases does not exceed $3\cdot10^{5}$

----- Sample Input 1 ------ 
1
10
15 30 15 5 3 15 3 3 5 5
1 2
1 5
2 3
2 4
5 6
5 7
5 8
7 9
7 10
----- Sample Output 1 ------ 
33
----- explanation 1 ------ 
The tree from the sample is as follows.

![tree_{basic}]

If vertex $v = 7$ is chosen, vertices $1$, $5$ and $7$ are removed.

![tree_{remove}]

The resulting forest contains five connected components $\{8\}, \{6\}, \{10\}, \{9\}$ and $\{2, 3, 4\}$.

![tree_{value}]

The beauties of the connected components are $3$, $15$, $5$, $5$ and $5$ respectively. Thus the answer is $3 + 15 + 5 + 5 + 5 = 33$.

It can be shown that this is the maximum value possible for any choice of $v$.

Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Number theory

Tree algorithms

Dynamic programming

Mathematics

Data structures
Skill types: Dynamic programming

Data structures

Starter code:

Solutions:
import sys
import math

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))

def docase():
	[n] = get_ints()
	aa = get_ints()
	ee = [list() for _ in range(0, n)]
	for _ in range(1, n):
		[u, v] = get_ints()
		if v != 1:
			ee[u - 1].append(v)
		if u != 1:
			ee[v - 1].append(u)
	stack = [(1, 0, ee[0], aa[0], 0, 0)]
	while stack:
		(a, b, cc, gnode, gsum, best) = stack[-1]
		if cc:
			c = cc.pop()
			if c == b:
				continue
			stack.append((c, a, ee[c - 1], aa[c - 1], 0, 0))
		else:
			stack.pop()
			g = gnode
			s = max(gsum, gsum + best)
			if not stack:
				print(s)
			else:
				(a, b, cc, gnode, gsum, best) = stack.pop()
				diff = s - g
				if gsum != 0 and diff < best:
					diff = best
				stack.append((a, b, cc, math.gcd(gnode, g), gsum + g, diff))
[t] = get_ints()
for _ in range(0, t):
	docase()


import sys
import math

class TreeNode:

	def init(self, value):
		self.value = value
		self.gcd = value
		self.gcdSumOFChildren = 0
result = 0

def solve():
	n = int(input())
	ValuesOfNode = list(map(int, input().split()))
	values = {}
	for i in range(1, n + 1):
		values[i] = TreeNode()
		values[i].value = ValuesOfNode[i - 1]
		values[i].gcd = ValuesOfNode[i - 1]
		values[i].gcdSumOFChildren = 0
	g = {}
	for i in range(1, n + 1):
		g[i] = []
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		g[b].append(a)
		g[a].append(b)

	def helper(curr, parent):
		sumofgcd = 0
		for child in g[curr]:
			if child != parent:
				helper(child, curr)
				values[curr].gcd = math.gcd(values[curr].gcd, values[child].gcd)
				sumofgcd += values[child].gcd
		values[curr].gcdSumOFChildren = sumofgcd
	helper(1, -1)
	global result
	result = 0

	def helper2(curr, parent, sum):
		sum += values[curr].gcdSumOFChildren
		global result
		result = max(result, sum)
		for child in g[curr]:
			if child != parent:
				helper2(child, curr, sum - values[child].gcd)
	helper2(1, -1, 0)
	print(result)
sys.setrecursionlimit(10 ** 6)
numberOfTestCases = int(input())
for i in range(numberOfTestCases):
	solve()


import sys

class Node:

	def __init__(self, val):
		self.val = val
		self.gcd = val
		self.sumOfGcdChildren = 0

	def __str__(self):
		return f' {self.gcd} {self.sumOfGcdChildren} {self.val}'

def __gcd(a, b):
	if b == 0:
		return a
	return __gcd(b, a % b)
ans = 0

def run():
	n = int(input())
	nodeval = list(map(int, input().split()))
	nodes = {}
	for i in range(1, n + 1):
		nodes[i] = Node(nodeval[i - 1])
	graph = {}
	for i in range(1, n + 1):
		graph[i] = []
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		graph[a].append(b)
		graph[b].append(a)

	def dfs(curr, parent):
		sumofgcd = 0
		for child in graph[curr]:
			if child != parent:
				dfs(child, curr)
				nodes[curr].gcd = __gcd(nodes[curr].gcd, nodes[child].gcd)
				sumofgcd += nodes[child].gcd
		nodes[curr].sumOfGcdChildren = sumofgcd
	dfs(1, -1)
	global ans
	ans = 0

	def dfs2(curr, parent, sum):
		sum += nodes[curr].sumOfGcdChildren
		global ans
		ans = max(ans, sum)
		for child in graph[curr]:
			if child != parent:
				dfs2(child, curr, sum - nodes[child].gcd)
	dfs2(1, -1, 0)
	print(ans)
sys.setrecursionlimit(10 ** 6)
test = int(input())
for i in range(test):
	run()


def gcd(x, y):
	if y > x:
		(x, y) = (y, x)
	if y == 0:
		return x
	if x == 0:
		return y
	x = x % y
	return gcd(y, x)

class Node:
	parent = None

	def __init__(self, value, index):
		self.value = value
		self.index = index
		self.child = []
		self.tree_gcd = None
		self.beauty_ = None

	def gcd_of_tree(self):
		if self.tree_gcd != None:
			return self.tree_gcd
		x = self.value
		for c in self.child:
			x = gcd(x, c.gcd_of_tree())
		self.tree_gcd = x
		return x

	def beauty(self):
		if self.beauty_ != None:
			return self.beauty_
		if self.parent == None:
			sum_ = 0
		else:
			sum_ = self.parent.beauty()
			sum_ = sum_ - self.gcd_of_tree()
		for c in self.child:
			sum_ = sum_ + c.gcd_of_tree()
		self.beauty_ = sum_
		return sum_

def assign_parent_child(stack):
	while len(stack) > 0:
		(v, p) = stack.pop()
		v.parent = p
		if p != None:
			v.child.remove(p)
		for c in v.child:
			stack.append((c, v))

def bfs(stack, pointer):
	while len(stack) > pointer:
		for c in stack[pointer].child:
			stack.append(c)
		pointer = pointer + 1
t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	arr = list(map(int, input().split()))
	nodes = []
	for i in range(n):
		node = Node(arr[i], i)
		nodes.append(node)
	for q in range(n - 1):
		(i, j) = list(map(int, input().split()))
		i = i - 1
		j = j - 1
		nodes[i].child.append(nodes[j])
		nodes[j].child.append(nodes[i])
	stack = []
	stack.append((nodes[0], None))
	assign_parent_child(stack)
	stack = [nodes[0]]
	bfs(stack, 0)
	for i in range(len(stack) - 1, -1, -1):
		stack[i].gcd_of_tree()
	max_ = 1
	stack = []
	stack.append(nodes[0])
	while len(stack) > 0:
		node = stack.pop()
		if len(node.child) != 0:
			curr = node.beauty()
			if max_ < curr:
				max_ = curr
			stack.extend(node.child)
	print(max_)


from math import gcd
from functools import reduce

def findgcdtree(vals):
	return reduce(gcd, vals)

class TreeNode:

	def __init__(self, val, num):
		self.val = val
		self.num = num
		self.children = list()
		self.visited = 0
		self.parent = None
		self.gcd = None
		self.beauty = 0

	def addLink(self, node):
		self.children.append(node)

	def maxBeau(self):
		beautyMax = self.beauty
		for x in self.children:
			beautyMax = max(beautyMax, x.maxBeau())
		return beautyMax

def findMaxTree(root):
	nodesToAns = [root]
	maxBeau = 0
	while nodesToAns:
		node = nodesToAns.pop()
		maxBeau = max(node.beauty, maxBeau)
		nodesToAns.extend(node.children)
	return maxBeau

def calcBeaut89(root):
	nodesToAns = [root]
	while nodesToAns:
		node = nodesToAns.pop()
		if node.parent != None:
			node.beauty += node.parent.beauty
			node.beauty -= node.gcd
		for x in node.children:
			node.beauty += x.gcd
			nodesToAns.append(x)

def gcdtree(root):
	nodesToAns = [root]
	while nodesToAns:
		node = nodesToAns.pop()
		notDone = list()
		vals = [node.val]
		for x in node.children:
			if x.gcd == None:
				notDone.append(x)
			else:
				vals.append(x.gcd)
		if notDone:
			nodesToAns.append(node)
			nodesToAns.extend(notDone)
		else:
			node.gcd = findgcdtree(vals)
case = int(input())
for k in range(case):
	nodes = dict()
	n = int(input())
	vals = list(map(int, input().split(' ')))
	for i in range(n):
		node = TreeNode(vals[i], i + 1)
		nodes[i + 1] = node
	for i in range(0, n - 1):
		(a, b) = map(int, input().split(' '))
		nodes[a].addLink(nodes[b])
		nodes[b].addLink(nodes[a])
	root = nodes[1]
	nodesToAns = [root]
	while nodesToAns:
		node = nodesToAns.pop()
		for x in node.children:
			x.parent = node
			x.children.remove(node)
		nodesToAns.extend(node.children)
	gcdtree(root)
	calcBeaut89(root)
	print(findMaxTree(root))


from math import gcd
from functools import reduce

def findgcd(vals):
	return reduce(gcd, vals)

class Node:

	def __init__(self, val, num):
		self.val = val
		self.num = num
		self.links = []
		self.visited = 0
		self.parent = None
		self.gcd = None
		self.beauty = 0

	def addLink(self, node):
		self.links.append(node)

	def __str__(self):
		string = str(self.num)
		string += ' -> '
		for x in self.links:
			string += str(x.num) + ' '
		return string

	def printTreeAsRoot(self):
		nodesToCheck = [self]
		while nodesToCheck:
			x = nodesToCheck.pop(0)
			print(x)
			nodesToCheck.extend(x.links)

	def printTreegcds(self):
		print(str(self.num) + ': ' + str(self.gcd))
		for x in self.links:
			x.printTreegcds()

	def printTreeBeauties(self):
		print(str(self.num) + ': ' + str(self.beauty))
		for x in self.links:
			x.printTreeBeauties()

	def calcgcd(self):
		vals = [self.val]
		for x in self.links:
			if x.gcd == None:
				x.calcgcd()
			vals.append(x.gcd)
		self.gcd = findgcd(vals)

	def calculateBeauty(self):
		if self.parent != None:
			self.beauty = self.parent.beauty - self.gcd
		for x in self.links:
			self.beauty += x.gcd
		for x in self.links:
			x.calculateBeauty()

	def maxBeauty(self):
		beautyMax = self.beauty
		for x in self.links:
			beautyMax = max(beautyMax, x.maxBeauty())
		return beautyMax

def findMaxBeauty(root):
	nodesToCheck = [root]
	maxBeauty = 0
	while nodesToCheck:
		node = nodesToCheck.pop()
		maxBeauty = max(node.beauty, maxBeauty)
		nodesToCheck.extend(node.links)
	return maxBeauty

def calcBeauties(root):
	nodesToCheck = [root]
	while nodesToCheck:
		node = nodesToCheck.pop()
		if node.parent != None:
			node.beauty += node.parent.beauty
			node.beauty -= node.gcd
		for x in node.links:
			node.beauty += x.gcd
			nodesToCheck.append(x)

def calcgcds(root):
	nodesToCheck = [root]
	while nodesToCheck:
		node = nodesToCheck.pop()
		notDone = []
		vals = [node.val]
		for x in node.links:
			if x.gcd == None:
				notDone.append(x)
			else:
				vals.append(x.gcd)
		if notDone:
			nodesToCheck.append(node)
			nodesToCheck.extend(notDone)
		else:
			node.gcd = findgcd(vals)
t = int(input())
for _ in range(t):
	nodes = {}
	n = int(input())
	vals = list(map(int, input().split()))
	for i in range(n):
		node = Node(vals[i], i + 1)
		nodes[i + 1] = node
	for _ in range(n - 1):
		(l1, l2) = list(map(int, input().split()))
		nodes[l1].addLink(nodes[l2])
		nodes[l2].addLink(nodes[l1])
	root = nodes[1]
	nodesToCheck = [root]
	while nodesToCheck:
		node = nodesToCheck.pop()
		for x in node.links:
			x.parent = node
			x.links.remove(node)
		nodesToCheck.extend(node.links)
	calcgcds(root)
	calcBeauties(root)
	print(findMaxBeauty(root))


from math import gcd
import sys
sys.setrecursionlimit(10 ** 6)

def calc_gcds(tree, A, current_node=1, previous_node=0, gcds=dict()):
	gcds[current_node] = A[current_node - 1]
	for x in tree[current_node]:
		if x == previous_node:
			continue
		gcds[current_node] = gcd(gcds[current_node], calc_gcds(tree, A, x, current_node, gcds)[x])
	return gcds

def solve(tree, gcds, current_node=1, previous_node=0):
	s = 0
	for x in tree[current_node]:
		if x == previous_node:
			continue
		s += gcds[x]
	ans = []
	for x in tree[current_node]:
		if x == previous_node:
			continue
		ans.append(s - gcds[x] + solve(tree, gcds, x, current_node))
	return max([s] + ans)
for _ in range(int(input())):
	N = int(input())
	A = [int(x) for x in input().split()]
	tree = dict()
	for _i in range(N - 1):
		(u, v) = [int(x) for x in input().split()]
		if u not in tree:
			tree[u] = []
		if v not in tree:
			tree[v] = []
		tree[u].append(v)
		tree[v].append(u)
	if not tree:
		print(0)
		continue
	gcds = calc_gcds(tree, A)
	print(solve(tree, gcds))


import math
from sys import setrecursionlimit
setrecursionlimit(1999999999)

def get_group_gcds(node, parent, tree, values, all_group_values, cut_group_values):
	group_value = values[node]
	summ = 0
	for i in tree[node]:
		if i != parent:
			current = get_group_gcds(i, node, tree, values, all_group_values, cut_group_values)
			summ += current
			group_value = math.gcd(group_value, current)
	all_group_values[node] = group_value
	cut_group_values[node] = summ
	return group_value

def find_beauty(node, parent, su, tree, values, all_group_values, cut_group_values):
	global beauty
	beauty = max(beauty, su)
	for i in tree[node]:
		if i != parent:
			find_beauty(i, node, su - all_group_values[i] + cut_group_values[i], tree, values, all_group_values, cut_group_values)

def answer(n, tree, values):
	global beauty
	beauty = 0
	all_group_values = [0] * n
	cut_group_values = [0] * n
	ROOT = 1 - 1
	ROOT_PARENT = ROOT - 1
	get_group_gcds(ROOT, ROOT_PARENT, tree, values, all_group_values, cut_group_values)
	find_beauty(0, -1, cut_group_values[0], tree, values, all_group_values, cut_group_values)
	return beauty
for q in range(int(input())):
	n = int(input())
	values = [int(e) for e in input().split()]
	tree = {i: [] for i in range(n)}
	for i in range(n - 1):
		link = [int(e) - 1 for e in input().split()]
		tree[link[0]] += [link[1]]
		tree[link[1]] += [link[0]]
	print(answer(n, tree, values))


import sys
sys.setrecursionlimit(350000)

def gcd(a, b):
	if a % b == 0:
		return b
	return gcd(b, a % b)

def dps(node, parent):
	visited[node] = True
	dp[node] = dp[parent] - g_st[node] + g_sum[node]
	for child in adj[node]:
		if not visited[child]:
			if child != parent:
				dps(child, node)

def dfs_2(node, parent):
	visited[node] = False
	for child in adj[node]:
		if visited[child]:
			if child != parent:
				g_sum[node] += g_st[child]
				dfs_2(child, node)

def dfs(node, parent):
	visited[node] = True
	g_st[node] = A[node - 1]
	for child in adj[node]:
		if child != parent:
			if not visited[child]:
				if g_st[child] != 0:
					g_st[node] = gcd(g_st[node], g_st[child])
				else:
					g_st[node] = gcd(g_st[node], dfs(child, node))
	return g_st[node]
for _ in range(int(input())):
	N = int(input())
	A = [int(i) for i in input().split()]
	if N == 1:
		print(0)
	else:
		adj = {}
		for i in range(N):
			adj[i + 1] = []
		for i in range(N - 1):
			(u, v) = [int(i) for i in input().split()]
			adj[u].append(v)
			adj[v].append(u)
		visited = [False] * (N + 1)
		g_st = [0] * (N + 1)
		g_sum = [0] * (N + 1)
		dp = [0] * (N + 1)
		dfs(1, 0)
		dfs_2(1, 0)
		dp[0] = g_st[1]
		dps(1, 0)
		print(max(dp))


from queue import Queue
import sys
sys.setrecursionlimit(10 ** 7)
import math

def dfs(i):
	vistited[i] = True
	g = arr[i]
	for j in tree[i]:
		if not vistited[j]:
			g = math.gcd(g, dfs(j))
	gcd_arr[i] = g
	return g

def bfs(i):
	q = Queue()
	q.put(i)
	while not q.empty():
		x = q.get()
		g = 0
		vistited[x] = True
		if len(tree[x]) == 1:
			continue
		for j in tree[x]:
			if not vistited[j]:
				q.put(j)
			g += gcd_arr[j]
		gcd_arr[x] = g - gcd_arr[x]
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	tree = [[] for i in range(n)]
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		tree[u - 1].append(v - 1)
		tree[v - 1].append(u - 1)
	vistited = [False] * n
	gcd_arr = [0] * n
	dfs(0)
	a = 0
	for i in tree[0]:
		a += gcd_arr[i]
	gcd_arr[0] = a
	vistited = [False] * n
	for i in tree[0]:
		vistited[0] = True
		bfs(i)
	print(max(gcd_arr))


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
T = int(input())
for _ in range(T):
	N = int(input())
	vertices = list(map(int, input().split()))
	neighbours = [[] for _ in range(N)]
	children = [[] for _ in range(N)]
	for _ in range(N - 1):
		(u, v) = list(map(int, input().split()))
		neighbours[u - 1].append(v - 1)
		neighbours[v - 1].append(u - 1)
	q = [0]
	l = []
	visited = [False] * N
	while q:
		u = q.pop()
		visited[u] = True
		children[u] = [v for v in neighbours[u] if not visited[v]]
		q.extend(children[u])
		l.append(u)
	gcds = [None] * N
	for u in reversed(l):
		g = vertices[u]
		for v in children[u]:
			g = gcd(g, gcds[v])
		gcds[u] = g
	above = [0] * N
	below = [0] * N
	for u in l:
		below[u] = sum((gcds[v] for v in children[u]))
		for v in children[u]:
			above[v] = above[u] + below[u] - gcds[v]
	m = max((above[u] + below[u] for u in l))
	print(m)


import sys
sys.setrecursionlimit(1000000)

def mi():
	return map(int, input().split())

def li():
	return list(mi())

def si():
	return str(input())

def ni():
	return int(input())
from math import gcd

def findgcd(g, nodegcd, node, a, visited):
	ans = a[node - 1]
	for i in g[node]:
		if i not in visited:
			visited.add(i)
			ans = gcd(findgcd(g, nodegcd, i, a, visited), ans)
	nodegcd[node] = ans
	return ans

def findpath(g, path, node, visited, curr, nodegcd):
	for i in g[node]:
		if i not in visited:
			visited.add(i)
			ans = int(curr)
			ans -= nodegcd[i]
			for j in g[i]:
				if j not in visited:
					ans += nodegcd[j]
			path[i] = ans
			findpath(g, path, i, visited, ans, nodegcd)
for t in range(int(input())):
	n = ni()
	a = li()
	g = []
	for i in range(n + 1):
		g.append([])
	for i in range(n - 1):
		(x, y) = mi()
		g[x].append(y)
		g[y].append(x)
	nodegcd = dict()
	findgcd(g, nodegcd, 1, a, {1})
	path = dict()
	path[1] = 0
	for i in g[1]:
		path[1] += nodegcd[i]
	findpath(g, path, 1, {1}, path[1], nodegcd)
	print(max(path.values()))


from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(4 * 10 ** 5)
inp = lambda : list(map(int, input().split()))

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def solve(p, prev, take):
	if dp[p][take] != -1:
		return dp[p][take]
	if take == 0:
		gcdval = a[p - 1]
		for i in child[p]:
			if i == prev:
				continue
			gcdval = gcd(gcdval, solve(i, p, 0))
		dp[p][take] = gcdval
		return gcdval
	else:
		total = 0
		for i in child[p]:
			if i == prev:
				continue
			total += solve(i, p, 0)
		bestans = total
		for i in child[p]:
			if i == prev:
				continue
			curans = total - solve(i, p, 0) + solve(i, p, 1)
			bestans = max(bestans, curans)
		dp[p][take] = bestans
		return bestans
for T in range(int(input())):
	n = int(input())
	a = inp()
	child = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = inp()
		child[u].append(v)
		child[v].append(u)
	dp = [[-1, -1] for i in range(n + 1)]
	ans = max(solve(1, -1, 0), solve(1, -1, 1))
	print(ans)