Sardar Khan has finally decided to attack Ramadhir - he will bomb one of Ramadhir's businesses in Wasseypur. Sardar Khan knows that Ramadhir has N businesses (numbered 1 to N) and that there are N - 1 roads connecting pairs of these businesses in such a way that all businesses are connected. Further, Sardar knows that each business has a specific value - the i-th business has value A_{i}.

When Sardar Khan destroys a business, he also destroys every road directly connected to it.
Formally, destroying business v also destroys all existing roads of the form (u, v).

Sardar thinks that the damage dealt to Ramadhir upon destroying business v equals the sum of the [greatest common divisors] of every remaining maximal connected set of businesses. More formally,
* Let the connected components of the graph obtained on deleting v and edges incident to it be C_{1}, C_{2}, \dots, C_{k}.
* Define \gcd(C_{i}) to be \gcd(A_{i_{1}}, A_{i_{2}}, \dots, A_{i_{r}}) where C_{i} consists of vertices i_{1}, i_{2}, \dots, i_{r}.
* The damage caused by destroying v is then \sum_{i = 1}^k \gcd(C_{i}).

Sardar Khan wants to maximize the damage he deals. Can you find the maximum possible damage he can achieve, given that he destroys exactly one business?

If the process of computing damage is still unclear, please refer to sample test cases for an explained example.

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

- The first line of input contains an integer T, denoting the total number of test cases. The description of T test cases follows.
- The first line of each test case contains an integer N, denoting the number of businesses Ramadhir owns.
- Each of the next N-1 lines contains 2 integers a and b, denoting a road between businesses a and b.
- Finally, the last line of each test case contains N space-separated positive integers A_{1}, A_{2}, \ldots, A_{N}, where A_{i} is the value of the i-th business.

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

- For each test case, output a single line containing one integer - the maximum possible damage that Sardar Khan can deal.

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

$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases will not exceed $5 \cdot 10^{5}$.
- It is guaranteed that the given roads connect every business.

----- Sample Input 1 ------ 
1
5
1 2
1 3
3 4
3 5
4 6 8 12 15
----- Sample Output 1 ------ 
29
----- explanation 1 ------ 
* If business $1$ is bombed, the remaining connected components are $\{(2), (3, 4, 5)\}$. This gives a damage of $\gcd(A_{2}) + \gcd(A_{3}, A_{4}, A_{5}) = 6 + 1 = 7$.
* If business $2$ is bombed, the remaining connected components are $\{(1, 3, 4, 5)\}$. This gives a damage of $\gcd(A_{1}, A_{3}, A_{4}, A_{5}) = 1$.
* If business $3$ is bombed, the remaining connected components are $\{(1, 2), (4), (5)\}$. This gives a damage of $\gcd(A_{1}, A_{2}) + \gcd(A_{4}) + \gcd(A_{5}) = 2 + 12 + 15 = 29$.
* If business $4$ is bombed, the remaining connected components are $\{(1, 2, 3, 5)\}$. This gives a damage of $\gcd(A_{1}, A_{2}, A_{3}, A_{5}) = 1$.
* If business $5$ is bombed, the remaining connected components are $\{(1, 2, 3, 4)\}$. This gives a damage of $\gcd(A_{1}, A_{2}, A_{3}, A_{4}) = 2$.

Clearly, bombing business $3$ gives the maximum possible damage, that being 29.

Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Preprocessing

Range queries

Number theory

Tree algorithms

Mathematics

Data structures

Tree queries
Skill types: Data structures

Range queries

Starter code:

Solutions:
import sys
from math import gcd
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	n = int(input())
	adj = [[] for i in range(n)]
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		adj[a - 1].append(b - 1)
		adj[b - 1].append(a - 1)
	v = list(map(int, input().split()))

	def solve(i, p):
		g[i] = v[i]
		for j in adj[i]:
			if j != p:
				solve(j, i)
				g[i] = gcd(g[i], g[j])
	g = [0] * n
	solve(0, -1)

	def dfs(i, p, gp):
		d = gp
		a = []
		b = []
		child = []
		for j in adj[i]:
			if j != p:
				d += g[j]
				a.append(g[j])
				b.append(g[j])
				child.append(j)
		ans[0] = max(ans[0], d)
		t = len(a)
		for j in range(1, t):
			a[j] = gcd(a[j], a[j - 1])
		for j in reversed(range(t - 1)):
			b[j] = gcd(b[j], b[j + 1])
		for k in range(t):
			ngp = gcd(gp, v[i])
			if k > 0:
				ngp = gcd(ngp, a[k - 1])
			if k < t - 1:
				ngp = gcd(ngp, b[k + 1])
			dfs(child[k], i, ngp)
	ans = [0]
	dfs(0, -1, 0)
	print(ans[0])


from math import gcd
from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
for i in range(int(input())):
	n = int(input())
	adj = [[] for i in range(n)]
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		x -= 1
		y -= 1
		adj[x].append(y)
		adj[y].append(x)
	a = list(map(int, input().split()))
	subgcd = [0] * n
	vis = [0] * n

	def dfs(src):
		vis[src] = 1
		g = a[src]
		for i in adj[src]:
			if vis[i] == 0:
				g = gcd(g, dfs(i))
		subgcd[src] = g
		return g
	dfs(0)
	vis = [0] * n
	ans = [0]

	def dfs1(src, parg):
		cur_ans = parg
		vis[src] = 1
		ch = []
		p = []
		s = []
		for i in adj[src]:
			if vis[i] == 0:
				ch.append(i)
				p.append(subgcd[i])
				s.append(subgcd[i])
				cur_ans += subgcd[i]
		l = len(p)
		for i in range(1, l):
			p[i] = gcd(p[i - 1], p[i])
		for i in range(l - 2, -1, -1):
			s[i] = gcd(s[i + 1], s[i])
		ans[0] = max(ans[0], cur_ans)
		for i in range(l):
			new_parg = a[src]
			if i > 0:
				new_parg = gcd(new_parg, p[i - 1])
			if i < l - 1:
				new_parg = gcd(new_parg, s[i + 1])
			new_parg = gcd(new_parg, parg)
			dfs1(ch[i], new_parg)
	dfs1(0, 0)
	print(ans[0])


import math
import sys
H = 1000000000 + 7
sys.setrecursionlimit(10000000)
for _ in range(int(input())):
	n = int(input())
	adj = [[] for i in range(n)]
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		adj[a - 1].append(b - 1)
		adj[b - 1].append(a - 1)
	v = list(map(int, input().split()))

	def solve(i, p):
		g[i] = v[i]
		for j in adj[i]:
			if j != p:
				solve(j, i)
				g[i] = math.gcd(g[i], g[j])
	g = [0] * n
	solve(0, -1)

	def dfs(i, p, gp):
		d = gp
		a = []
		b = []
		child = []
		for j in adj[i]:
			if j != p:
				d += g[j]
				a.append(g[j])
				b.append(g[j])
				child.append(j)
		ans[0] = max(ans[0], d)
		t = len(a)
		for j in range(1, t):
			a[j] = math.gcd(a[j], a[j - 1])
		for j in range(t - 2, -1, -1):
			b[j] = math.gcd(b[j], b[j + 1])
		for k in range(t):
			ngp = math.gcd(gp, v[i])
			if k > 0:
				ngp = math.gcd(ngp, a[k - 1])
			if k < t - 1:
				ngp = math.gcd(ngp, b[k + 1])
			dfs(child[k], i, ngp)
	ans = [0]
	dfs(0, -1, 0)
	print(ans[0])


from collections import defaultdict, deque
from math import gcd
from sys import stdin, setrecursionlimit
setrecursionlimit(200001)

def solve():
	global timer
	results = []
	for _ in range(int(stdin.readline().strip())):
		N = int(stdin.readline().strip())
		Road = defaultdict(list)
		Parent = [0] * (N + 1)
		for _ in range(N - 1):
			(a, b) = map(int, stdin.readline().strip().split())
			Road[a].append(b)
			Road[b].append(a)
		A = [0] + list(map(int, stdin.readline().strip().split()))
		euler_tour = []
		gcd_subtree = [0] * (N + 1)
		_in = [0] * (N + 1)
		_out = [0] * (N + 1)
		timer = 1

		def dfs(G, Parent, A, gcd_subtree, euler_tour, _in, _out, node, p=-1, visited=set()):
			global timer
			euler_tour.append(node)
			visited.add(node)
			gcd_subtree[node] = A[node]
			Parent[node] = p
			_in[node] = timer
			timer += 1
			for child in G[node]:
				if child not in visited:
					gcd_subtree[node] = gcd(dfs(G, Parent, A, gcd_subtree, euler_tour, _in, _out, child, node, visited), gcd_subtree[node])
					euler_tour.append(node)
			_out[node] = timer
			timer += 1
			return gcd_subtree[node]
		dfs(Road, Parent, A, gcd_subtree, euler_tour, _in, _out, 1)
		forward = [0] * (2 * N + 1)
		backward = [0] * (2 * N + 1)
		forward[1] = backward[-1] = A[1]
		for i in range(2, len(euler_tour) + 1):
			forward[i] = gcd(forward[i - 1], A[euler_tour[i - 1]])
		for i in range(len(euler_tour) - 1, -1, -1):
			backward[i] = gcd(backward[i + 1], A[euler_tour[i - 1]])
		ans = 1
		for i in list(Road.keys()):
			children = []
			for child in Road[i]:
				if child != Parent[i]:
					children.append(gcd_subtree[child])
			if len(children):
				temp = sum(children)
				if i != 1:
					temp1 = gcd(forward[_in[i] - 1], backward[_out[i] + 1])
					ans = max(ans, temp + temp1)
				else:
					ans = max(ans, temp)
			else:
				temp = gcd(forward[_in[i] - 1], backward[_out[i] + 1])
				ans = max(ans, temp)
		results.append(ans)
	print('\n'.join(map(str, results)))
solve()


import math
from collections import defaultdict
from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)
t = int(input())
for _ in range(t):
	n = int(input())
	graph = defaultdict(list)
	for _ in range(n - 1):
		(a, b) = [int(i) for i in input().split()]
		graph[a].append(b)
		graph[b].append(a)
	arr = [int(i) for i in input().split()]
	memo = [0] * (n + 1)

	def helper(node, prev):
		ans = 0
		temp = []
		for ele in graph[node]:
			if ele == prev:
				continue
			temp.append(helper(ele, node))
		ret = arr[node - 1]
		for ele in temp:
			ret = math.gcd(ele, ret)
		memo[node] = ret
		return ret
	helper(1, n + 1)
	final_ans = []

	def helper2(node, prev, top_gcd):
		pref = []
		suff = []
		for ele in graph[node]:
			if ele == prev:
				continue
			elif len(pref) == 0:
				pref.append(memo[ele])
			else:
				pref.append(memo[ele])
				pref[-1] = math.gcd(pref[-1], pref[-2])
		for ele in graph[node][::-1]:
			if ele == prev:
				continue
			elif len(suff) == 0:
				suff.append(memo[ele])
			else:
				suff.append(memo[ele])
				suff[-1] = math.gcd(suff[-1], suff[-2])
		suff = suff[::-1]
		if top_gcd is not None:
			curr2 = top_gcd
			start = math.gcd(top_gcd, arr[node - 1])
		else:
			curr2 = 0
			start = arr[node - 1]
		i = 0
		for ele in graph[node]:
			curr = start
			if ele == prev:
				continue
			else:
				temp1 = i - 1
				if temp1 >= 0:
					curr = math.gcd(curr, pref[temp1])
				temp1 = i + 1
				if temp1 < len(pref):
					curr = math.gcd(curr, suff[temp1])
				helper2(ele, node, curr)
				curr2 += memo[ele]
				i += 1
		final_ans.append(curr2)
		return
	helper2(1, n + 1, None)
	print(max(final_ans))


import math
from heapq import heappush, heappop, heapify
import random
import string
from collections import deque
from bisect import bisect, bisect_left, bisect_right, insort
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
H = 1000000000 + 7
sys.setrecursionlimit(10000000)
for _ in range(I()):
	n = I()
	adj = [[] for i in range(n)]
	for i in range(n - 1):
		(a, b) = M()
		adj[a - 1].append(b - 1)
		adj[b - 1].append(a - 1)
	v = L()

	def solve(i, p):
		g[i] = v[i]
		for j in adj[i]:
			if j != p:
				solve(j, i)
				g[i] = math.gcd(g[i], g[j])
	g = [0] * n
	solve(0, -1)

	def dfs(i, p, gp):
		d = gp
		a = []
		b = []
		child = []
		for j in adj[i]:
			if j != p:
				d += g[j]
				a.append(g[j])
				b.append(g[j])
				child.append(j)
		ans[0] = max(ans[0], d)
		t = len(a)
		for j in range(1, t):
			a[j] = math.gcd(a[j], a[j - 1])
		for j in range(t - 2, -1, -1):
			b[j] = math.gcd(b[j], b[j + 1])
		for k in range(t):
			ngp = math.gcd(gp, v[i])
			if k > 0:
				ngp = math.gcd(ngp, a[k - 1])
			if k < t - 1:
				ngp = math.gcd(ngp, b[k + 1])
			dfs(child[k], i, ngp)
	ans = [0]
	dfs(0, -1, 0)
	print(ans[0])


import sys
from collections import defaultdict
sys.setrecursionlimit(1000000)
from math import gcd

def dfs(node, parent):
	cgcd = 0
	cs = 0
	for j in d[node]:
		if j != parent:
			c = dfs(j, node)
			cs += c
			if c != 0:
				cgcd = gcd(cgcd, c)
	g[node][1] = [cgcd, cs]
	if cgcd == 0:
		cgcd = a[node - 1]
	else:
		cgcd = gcd(cgcd, a[node - 1])
	return cgcd

def dfs2(node, parent):
	cgcd = []
	nodes = []
	for j in d[node]:
		if j != parent:
			nodes.append(j)
			temp = g[j][1][0]
			if temp == 0:
				temp = a[j - 1]
			else:
				temp = gcd(temp, a[j - 1])
			cgcd.append(temp)
	if len(cgcd):
		lgcd = [cgcd[0]]
		for j in range(1, len(cgcd)):
			lgcd.append(gcd(lgcd[-1], cgcd[j]))
		rgcd = [cgcd[-1]]
		for j in range(len(cgcd) - 2, -1, -1):
			rgcd.append(gcd(rgcd[-1], cgcd[j]))
		c = 0
		rgcd.reverse()
		for j in nodes:
			ans = gcd(g[node][0], a[node - 1])
			if c - 1 >= 0:
				ans = gcd(ans, lgcd[c - 1])
			if c + 1 < len(rgcd):
				ans = gcd(ans, rgcd[c + 1])
			g[j][0] = ans
			dfs2(j, node)
			c += 1
for i in range(int(input())):
	d = defaultdict(list)
	n = int(input())
	g = [[-1, [0, 0]] for j in range(n + 5)]
	for j in range(n - 1):
		(a, b) = map(int, input().split())
		d[a].append(b)
		d[b].append(a)
	a = list(map(int, input().split()))
	ans = 0
	dfs(1, -1)
	g[1][0] = a[0]
	dfs2(1, 1)
	g[1][0] = 0
	for j in range(1, n + 1):
		ans = max(ans, g[j][0] + g[j][1][1])
	print(ans)