Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given a rooted tree with $N$ nodes (numbered $1$ through $N$); node $1$ is the root. For each valid $i$, the $i$-th node has a value $v_{i}$ and another parameter $m_{i}$.

A leaf is a node without sons. Let's denote the number of leaf nodes in the tree by $L$ and their numbers by $l_{1}, l_{2}, \ldots, l_{L}$, in increasing order. Then, for each valid $i$, let's define the *answer* for the leaf $l_{i}$ in the following way:
Consider the path from the root to $l_{i}$. For each node on this path (including the root and this leaf), choose a non-negative integer and multiply the value of this node by it.
Sum up the resulting values of all nodes on this path.
The answer $a_{i}$ for this leaf is defined as the maximum possible remainder of this sum modulo $m_{l_{i}}$.

Find the answers for all leaves.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
Each of the following $N-1$ lines contains two space-separated integers $x$ and $y$ denoting that nodes $x$ and $y$ are connected by an edge.
The next line contains $N$ space-separated integers $v_{1}, v_{2}, \ldots, v_{N}$.
The last line contains $N$ space-separated integers $m_{1}, m_{2}, \ldots, m_{N}$.

------  Output ------
For each test case, print a single line containing $L$ space-separated integers $a_{1}, a_{2}, \ldots, a_{L}$.

------  Constraints  ------
$1 ≤ T ≤ 8$
$2 ≤ N ≤ 10^{5}$
$1 ≤ x, y ≤ N$
$1 ≤ v_{i} ≤ 10^{18}$ for each valid $i$
$1 ≤ m_{i} ≤ 10^{18}$ for each valid $i$
the graph described on the input is a tree

------  Subtasks ------
Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
1
5
1 2
2 5
1 3
3 4
2 3 4 6 7
1 2 3 2 10
----- Sample Output 1 ------ 
0 9
----- explanation 1 ------ 
Example case 1: There are only two leaves, $l_{1} = 4$ and $l_{2} = 5$. The answers for them are $a_{1} = 0$ and $a_{2} = 9$.

Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Number theory

Tree algorithms

Mathematics

Data structures
Skill types: Data structures

Starter code:

Solutions:
from math import gcd
T = int(input())
for i in range(T):
	n = int(input())
	g = [set() for _ in range(n)]
	for j in range(n - 1):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		g[u].add(v)
		g[v].add(u)
	weight = list(map(int, input().split()))
	mod = list(map(int, input().split()))
	ans = [None] * n

	def dfs(node, v, p=None):
		f = 0
		for i in g[node]:
			if i != p:
				dfs(i, gcd(v, weight[i]), node)
				f = 1
		if f == 0:
			ans[node] = mod[node] - gcd(v, mod[node])
	dfs(0, weight[0])
	print(' '.join(map(str, [i for i in ans if i != None])))


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

def dfs(g, k, m, s, p, l, x, x1):
	for i in g[s]:
		if i != p:
			dfs(g, gcd(k, l[i]), m, i, s, l, x, x1)
	if len(g[s]) == 1 and s != 0:
		x1[s] = m[s] - gcd(k, m[s])
t = int(input())
while t > 0:
	n = int(input())
	g = {k: [] for k in range(n)}
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		g[u - 1].append(v - 1)
		g[v - 1].append(u - 1)
	c = 0
	li = []
	for i in g:
		if len(g[i]) == 1:
			li.append(i)
	l = list(map(int, input().split()))
	m = list(map(int, input().split()))
	x = [0 for i in range(n)]
	x1 = [-1 for i in range(n)]
	dfs(g, l[0], m, 0, -1, l, x, x1)
	for i in x1:
		if i != -1:
			print(i, end=' ')
	t = t - 1


t = int(input())
from collections import defaultdict
import queue
import sys
sys.setrecursionlimit(10 ** 5)

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

def dfs(i, graph, visited, g, v, leaves):
	if visited[i] == False:
		visited[i] = True
		isleaf = True
		for j in graph[i]:
			if visited[j] == False:
				g[j] = gcd(g[i], v[j])
				isleaf = False
				dfs(j, graph, visited, g, v, leaves)
		if isleaf:
			leaves.append(i)
for _ in range(t):
	n = int(input())
	graph = defaultdict(list)
	for i in range(n - 1):
		(u, v1) = list(map(int, input().split()))
		graph[u].append(v1)
		graph[v1].append(u)
	v = list(map(int, input().split()))
	m = list(map(int, input().split()))
	v = [0] + v
	m = [0] + m
	g = {}
	g[1] = v[1]
	leaves = []
	visited = {i: False for i in range(1, n + 1)}
	dfs(1, graph, visited, g, v, leaves)
	leaves.sort()
	for i in range(len(leaves)):
		l = leaves[i]
		print(m[l] - gcd(g[l], m[l]), end=' ')
	print()


import functools
from math import gcd
import sys
sys.setrecursionlimit(10 ** 5)

def fun():
	n = int(input())
	g = {x: [] for x in range(1, n + 1)}
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		g[u].append(v)
		g[v].append(u)
	a = list(map(int, input().split()))
	m = list(map(int, input().split()))
	ls = []

	def dfs(u, p, path=[]):
		path.append(a[u - 1])
		if len(g[u]) == 1 and p in g[u]:
			d = functools.reduce(gcd, path)
			ls.append([u, m[u - 1] - gcd(m[u - 1], d)])
		for v in g[u]:
			if v != p:
				dfs(v, u)
		path.pop()
	dfs(1, 0)
	for l in sorted(ls, key=lambda l: l[0]):
		print(l[1], end=' ')
for _ in range(int(input())):
	fun()


from math import gcd

def find_sum(v=1, p=1, g=0):
	for ee in graph[v]:
		if ee != p:
			find_sum(ee, v, gcd(g, arr_val[ee - 1]))
	if len(graph[v]) == 1 and v != 1:
		ans[v] = arr_rem[v - 1] - gcd(arr_rem[v - 1], g)
t = int(input().strip())
for i in range(t):
	n = int(input())
	graph = {}
	for e in range(1, n + 1):
		graph[e] = list()
	for e in range(n - 1):
		(a, b) = map(int, input().strip().split())
		graph[a].append(b)
		graph[b].append(a)
	arr_val = list(map(int, input().strip().split()))
	arr_rem = list(map(int, input().strip().split()))
	Visited = [False] * (n + 1)
	ans = [-1] * (n + 1)
	find_sum(1, 1, g=arr_val[0])
	for e in ans:
		if e != -1:
			print(e, end=' ')
	print()


from math import gcd
t = int(input())
for it in range(t):
	edge = {}
	f = []
	rev = {}
	n = int(input())
	val = []
	m = []
	for i in range(n - 1):
		(x, y) = map(int, input().split(' '))
		edge[x] = y
		rev[y] = x
	val = list(map(int, input().split(' ')))
	m = list(map(int, input().split(' ')))
	for i in range(2, n + 1):
		k = i
		res = 0
		if k not in edge.keys():
			res = val[k - 1]
			while k != 1:
				res = gcd(res, val[rev[k] - 1])
				k = rev[k]
			res = gcd(res, val[0])
			res = gcd(res, m[i - 1])
			res = m[i - 1] - res
			f.append(res % m[i - 1])
		elif k not in rev.keys():
			res = val[k - 1]
			while k != 1:
				res = gcd(res, val[edge[k] - 1])
				k = edge[k]
			res = gcd(res, val[0])
			res = gcd(res, m[i - 1])
			res = m[i - 1] - res
			f.append(res % m[i - 1])
	for i in f:
		print(i, end=' ')
	print('')


import sys
sys.setrecursionlimit(10 ** 8)
mod = 1000000007
get_arr = lambda : list(map(int, input().split()))
get_int = lambda : int(input())
get_ints = lambda : map(int, input().split())
get_str = lambda : input()
get_strs = lambda : input().split()
from math import gcd

def fn(root, leafs, d, vis, g):
	vis[root] = True
	isLeaf = True
	for i in d[root]:
		if vis[i] == False:
			isLeaf = False
			if g == None:
				fn(i, leafs, d, vis, A[root])
			else:
				fn(i, leafs, d, vis, gcd(g, A[root]))
	if isLeaf:
		leafs.append([root, gcd(g, A[root])])
for _ in range(get_int()):
	n = get_int()
	d = {}
	for i in range(1, n + 1):
		d[i] = []
	for i in range(n - 1):
		(u, v) = get_ints()
		d[u] += [v]
		d[v] += [u]
	A = [None] + get_arr()
	mods = [None] + get_arr()
	vis = [False] * (n + 1)
	leafs = []
	fn(1, leafs, d, vis, None)
	leafs = sorted(leafs)
	for i in leafs:
		(a, b) = (i[1], mods[i[0]])
		x = gcd(a, b)
		print((b // x - 1) * x, end=' ')
	print()


import sys

def gcd(a1, b1):
	if b1 == 0:
		return a1
	else:
		return gcd(b1, a1 % b1)

def dfs(b, c, a, m, s, p, x):
	x = gcd(x, a[s])
	if len(b[s]) == 1 and s != 0:
		c[s] = gcd(x, m[s])
	for i in b[s]:
		if i != p:
			dfs(b, c, a, m, i, s, x)
sys.setrecursionlimit(3000000)
t = int(input())
for t1 in range(t):
	n = int(input())
	b = {i: [] for i in range(0, n)}
	for i in range(n - 1):
		(u, v) = [int(j) for j in input().split()]
		b[u - 1].append(v - 1)
		b[v - 1].append(u - 1)
	a = [int(j) for j in input().split()]
	m = [int(j) for j in input().split()]
	c = [0 for j in range(n)]
	dfs(b, c, a, m, 0, -1, a[0])
	for i in range(1, n):
		if len(b[i]) == 1:
			print(m[i] - c[i], end=' ')
	print()


import sys
from math import gcd
sys.setrecursionlimit(100010)

def eval_gcd(L, mod):
	tem1 = L[0]
	for i in L:
		tem1 = gcd(tem1, i)
	return mod - gcd(tem1, mod)
for _ in range(int(input().strip(' '))):
	non = int(input())
	nary = [set() for _ in range(non + 1)]
	for _ in range(non - 1):
		(x, y) = map(int, input().strip(' ').split(' '))
		nary[x].add(y)
		nary[y].add(x)
	valit = list(map(int, input().strip(' ').split(' ')))
	paramit = list(map(int, input().strip(' ').split(' ')))
	leaf = []

	def dfs(node, par, path=[]):
		path.append(valit[node - 1])
		if len(nary[node]) == 1 and par in nary[node]:
			temp = path.copy()
			ans = eval_gcd(temp, paramit[node - 1])
			leaf.append([node, ans])
		for item in nary[node]:
			if item != par:
				dfs(item, node)
		path.pop()
	dfs(1, 0)
	leaf.sort(key=lambda w: w[0])
	for i in leaf:
		print(i[1], end=' ')


import sys
from math import gcd
sys.setrecursionlimit(100010)

def find_gcd(L, mod):
	tem = L[0]
	for k in L:
		tem = gcd(tem, k)
	return mod - gcd(tem, mod)
for _ in range(int(input().strip(' '))):
	n = int(input())
	graph = [set() for _ in range(n + 1)]
	for _ in range(n - 1):
		(x, y) = map(int, input().strip(' ').split(' '))
		graph[x].add(y)
		graph[y].add(x)
	val = list(map(int, input().strip(' ').split(' ')))
	param = list(map(int, input().strip(' ').split(' ')))
	leaf = []

	def getit(node, par, path=[]):
		path.append(val[node - 1])
		if len(graph[node]) == 1 and par in graph[node]:
			temp = path.copy()
			ans = find_gcd(temp, param[node - 1])
			leaf.append([node, ans])
		for ijk in graph[node]:
			if ijk != par:
				getit(ijk, node)
		path.pop()
	getit(1, 0)
	leaf.sort(key=lambda w: w[0])
	for i in leaf:
		print(i[1], end=' ')


class Node:

	def __init__(self, idx):
		self.idx = idx
		self.parent = None
		self.children = []
		self.v = None
		self.m = None
		self.gcd = 0

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def get_input_line():
	return input()

def solve2(node, value):
	if not node:
		return value
	value = gcd(node.v, value)
	if value == 1:
		return value
	node = node.parent
	return solve2(node, value)

def solve3(node, value):
	if not node:
		return value
	value = gcd(node.v, value)
	if value == 1:
		return value
	node = node.parent
	return solve3(node, value)

def solve(nodes):
	values = []
	for node in nodes:
		if not node.children:
			node.cd = solve2(node, node.m)
			values.append(str(node.m - node.cd))
	return ' '.join(values)

def dfs(edges, vs, ms, cd, values, current_index):
	cd = gcd(vs[current_index - 1], cd)
	cd2 = gcd(ms[current_index - 1], cd)
	values[current_index - 1] = ms[current_index - 1] - cd2
	for other_index in sorted(list(edges[current_index])):
		edges[other_index].remove(current_index)
		dfs(edges, vs, ms, cd, values, other_index)

def solve4(edges, vs, ms):
	current_index = 1
	values = [0] * len(vs)
	cd = vs[0]
	dfs(edges, vs, ms, cd, values, current_index)
	leaves = [i + 1 for i in range(len(vs)) if len(edges[i + 1]) == 0]
	return ' '.join([str(values[i - 1]) for i in leaves])

def main():
	test_count = int(get_input_line())
	for i in range(test_count):
		nodes_count = int(get_input_line())
		edges = {}
		for j in range(nodes_count - 1):
			(x, y) = list(map(int, get_input_line().split()))
			if x not in edges:
				edges[x] = set()
			edges[x].add(y)
			if y not in edges:
				edges[y] = set()
			edges[y].add(x)
		vs = list(map(int, get_input_line().split()))
		ms = list(map(int, get_input_line().split()))
		print(solve4(edges, vs, ms))
main()


__author__ = 'Ronald Kaiser'
__email__ = 'raios dot catodicos at gmail dot com'
from math import gcd

def solve(e, v, m, k):
	s = []
	stack = [0]
	while stack:
		cur = stack[-1]
		k[cur] = True
		if e[cur]:
			child = e[cur].pop()
			if k[child]:
				continue
			is_leaf[cur] = False
			v[child] = gcd(v[cur], v[child])
			stack.append(child)
		else:
			cur = stack.pop()
			if is_leaf[cur]:
				v[cur] = gcd(v[cur], m[cur])
				s.append((cur, m[cur] - v[cur]))
	print(' '.join(map(lambda x: str(x[1]), sorted(s, key=lambda x: x[0]))))
for _ in range(int(input())):
	N = int(input())
	e = [[] for _ in range(N)]
	for _ in range(N - 1):
		(x, y) = list(map(int, input().split()))
		e[x - 1].append(y - 1)
		e[y - 1].append(x - 1)
	v = list(map(int, input().split()))
	m = list(map(int, input().split()))
	k = [False for _ in range(N)]
	is_leaf = [True for _ in range(N)]
	solve(e, v, m, k)


from math import gcd
for i in range(int(input())):
	no_nodes = int(input())
	dic = dict()
	seta = set()
	setb = set()
	for i in range(no_nodes - 1):
		(a, b) = map(int, input().split())
		seta.add(a)
		setb.add(b)
		if a not in dic.keys():
			dic[a] = [b]
		else:
			dic[a].append(b)
		if b not in dic.keys():
			dic[b] = [a]
		else:
			dic[b].append(a)
	values = list(map(int, input().split()))
	modulo = list(map(int, input().split()))
	arr = []
	answer = dict()
	arr.append(1)
	temp = values[0]
	nodesvisited = set()
	l1 = []
	while arr:
		currentnode = arr.pop()
		if currentnode not in nodesvisited:
			nodesvisited.add(currentnode)
			for item in dic[currentnode]:
				if item not in nodesvisited:
					values[item - 1] = gcd(values[item - 1], values[currentnode - 1])
					if len(dic[item]) == 1 and item != 1:
						l1.append((item, modulo[item - 1] - gcd(modulo[item - 1], values[item - 1])))
					else:
						arr.append(item)
	l1.sort()
	for item in l1:
		print(item[1], end=' ')
	print('')


def traverse(i):
	visited.add(i)
	if len(tree[i]) == 1 and i != 0:
		leaf[i] = m[i] - gcd(gcdstore[i], m[i])
		return
	for j in range(len(tree[i])):
		if tree[i][j] not in visited:
			gcdstore[tree[i][j]] = gcd(gcdstore[i], v[tree[i][j]])
			traverse(tree[i][j])

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	(tree, gcdstore) = (dict(), dict())
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		(x, y) = (x - 1, y - 1)
		if x in tree:
			tree[x].append(y)
		else:
			tree[x] = [y]
		if y in tree:
			tree[y].append(x)
		else:
			tree[y] = [x]
	(v, m) = ([int(x) for x in input().split()], [int(x) for x in input().split()])
	leaf = [-1] * n
	visited = set()
	gcdstore[0] = v[0]
	traverse(0)
	for i in range(n):
		if leaf[i] != -1:
			print(leaf[i], end=' ')
	print()


from math import gcd
T = int(input())
for i in range(T):
	graph = {}
	children = {}
	N = int(input())
	for i in range(1, N + 1):
		graph[i] = []
		children[i] = []
	for i in range(N - 1):
		(x, y) = map(int, input().split())
		graph[x].append(y)
		graph[y].append(x)
	parent = {}

	def findParent(node):
		for i in graph[node]:
			try:
				temp = parent[i]
			except:
				if i != 1:
					parent[i] = node
					findParent(i)
	findParent(1)
	for i in range(1, N + 1):
		for j in graph[i]:
			if i == 1 or j != parent[i]:
				children[i].append(j)
	leaf = []
	for i in range(1, N + 1):
		if children[i] == []:
			leaf.append(i)
	value = {}
	ls = list(map(int, input().split()))
	for i in range(1, N + 1):
		value[i] = ls[i - 1]
	parameter = {}
	ls = list(map(int, input().split()))
	for i in range(1, N + 1):
		parameter[i] = ls[i - 1]

	def dfs(curnode):
		if curnode != 1:
			value[curnode] = gcd(value[curnode], value[parent[curnode]])
		for node in children[curnode]:
			dfs(node)
	dfs(1)
	for leafnode in leaf:
		print((parameter[leafnode] - gcd(value[leafnode], parameter[leafnode])) % parameter[leafnode], end=' ')
	print()


import math

def dfs(a, b, arr1, v, vector):
	arr1[a] = math.gcd(arr1[b], v[a])
	for i in range(len(vector[a])):
		if vector[a][i] == b:
			continue
		dfs(vector[a][i], a, arr1, v, vector)
t = int(input())
MAX = 100005
for _ in range(t):
	n = int(input())
	arr1 = [0] * MAX
	vector = []
	for i in range(MAX):
		vector.append([])
	for i in range(n - 1):
		(x, y) = list(map(int, input().split()))
		vector[x].append(y)
		vector[y].append(x)
	v = [0] + list(map(int, input().split()))
	m = [0] + list(map(int, input().split()))
	endnodes = []
	for i in range(2, n + 1):
		if len(vector[i]) == 1:
			endnodes.append(i)
	dfs(1, 0, arr1, v, vector)
	for i in range(len(endnodes)):
		ll = endnodes[i]
		ans = m[ll] - math.gcd(arr1[ll], m[ll])
		print(ans, end=' ')
	print


import sys
from math import gcd
sys.setrecursionlimit(100010)

def get_gcd(L, mod):
	temp = L[0]
	for i in L:
		temp = gcd(temp, i)
	return mod - gcd(temp, mod)
for _ in range(int(input().strip(' '))):
	number_of_nodes = int(input())
	tree = [set() for _ in range(number_of_nodes + 1)]
	for _ in range(number_of_nodes - 1):
		(x, y) = map(int, input().strip(' ').split(' '))
		tree[x].add(y)
		tree[y].add(x)
	value = list(map(int, input().strip(' ').split(' ')))
	parameter = list(map(int, input().strip(' ').split(' ')))
	leaves = []

	def dfs(node, par, path=[]):
		path.append(value[node - 1])
		if len(tree[node]) == 1 and par in tree[node]:
			temp = path.copy()
			ans = get_gcd(temp, parameter[node - 1])
			leaves.append([node, ans])
		for item in tree[node]:
			if item != par:
				dfs(item, node)
		path.pop()
	dfs(1, 0)
	leaves.sort(key=lambda w: w[0])
	for i in leaves:
		print(i[1], end=' ')


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

def dfs(node, v, val, m, visited, res, l):
	visited[node] = True
	flag = False
	for i in l.graph[node]:
		if not visited[i]:
			flag = True
			dfs(i, v, gcd(val, v[i]), m, visited, res, l)
	if not flag:
		res[node] = m[node] - gcd(val, m[node])
from collections import defaultdict

class Graph:

	def __init__(self):
		self.graph = defaultdict()

	def addEdge(self, u, v):
		if u not in self.graph:
			self.graph[u] = [v]
		else:
			self.graph[u].append(v)
		if v not in self.graph:
			self.graph[v] = [u]
		else:
			self.graph[v].append(u)
t = int(input())
for z in range(t):
	n = int(input())
	res = [-1] * (n + 1)
	l = Graph()
	for k in range(n - 1):
		(u, v) = map(int, input().split())
		l.addEdge(u, v)
	v = list(map(int, input().split()))
	m = list(map(int, input().split()))
	visited = [False] * (n + 1)
	v.insert(0, 0)
	m.insert(0, 0)
	dfs(1, v, v[1], m, visited, res, l)
	for i in range(1, len(res)):
		if res[i] != -1:
			print(res[i], end=' ')


check = []
from math import gcd

def bfs(root):
	visit = [False for i in range(n + 1)]
	queue = []
	leaf = []
	queue.append(root)
	gcdvalue = [0 for i in range(n + 1)]
	gcdvalue[root] = l[root - 1]
	visit[root] = True
	while queue:
		x = queue.pop(0)
		if len(g[x]) == 1 and x != 1:
			leaf.append(x)
		for i in g[x]:
			if visit[i] == False:
				queue.append(i)
				gcdvalue[i] = gcd(gcdvalue[x], l[i - 1])
				visit[i] = True
	leaf.sort()
	for i in leaf:
		print(m[i - 1] - gcd(m[i - 1], gcdvalue[i]), end=' ')
for _ in range(int(input())):
	n = int(input())
	global g
	g = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = list(map(int, input().split()))
		g[u].append(v)
		g[v].append(u)
	l = list(map(int, input().split()))
	m = list(map(int, input().split()))
	bfs(1)


visit = [0] * 100000

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

def dfs(s, edges, gcd_val, d, m, v):
	visit[s] = 1
	gcd_val = gcd(gcd_val, v[s])
	if len(edges[s]) == 1:
		d[s] = m[s] - gcd(gcd_val, m[s])
	for x in edges[s]:
		if visit[x] == 0:
			dfs(x, edges, gcd_val, d, m, v)
T = int(input())
for t in range(T):
	visit = [0] * 100000
	n = int(input())
	edges = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		edges[u].append(v)
		edges[v].append(u)
	v = list(map(int, input().split()))
	m = list(map(int, input().split()))
	d = {}
	dfs(0, edges, v[0], d, m, v)
	try:
		del d[0]
	except:
		pass
	for x in sorted(d):
		print(d[x], end=' ')
	print()


import math
import operator
import sys
sys.setrecursionlimit(200000)

def list_answer(x, a1, a2, b, c, s, m):
	list_x = b[x]
	c[x] = 1
	count = 0
	s = math.gcd(s, a1[x])
	l = []
	for i in range(len(list_x)):
		if c[list_x[i]] == 1:
			continue
		count = 1
		m = list_answer(list_x[i], a1, a2, b, c, s, m)
	if count == 1:
		return m
	else:
		m.append([x, s % a2[x]])
		return m
t = int(input())
for _ in range(t):
	n = int(input())
	b = [[] for x in range(n)]
	c = [0] * 100000
	for i in range(n - 1):
		(x, y) = [int(k) for k in input().split()]
		b[x - 1].append(y - 1)
		b[y - 1].append(x - 1)
	a1 = [int(x) for x in input().split()]
	a2 = [int(x) for x in input().split()]
	answer = list_answer(0, a1, a2, b, c, a1[0], [])
	answer = sorted(answer, key=operator.itemgetter(0))
	for i in range(len(answer)):
		k = answer[i][1] % a2[answer[i][0]]
		print(a2[answer[i][0]] - math.gcd(a2[answer[i][0]], k), end=' ')
	print('')


t = int(input().strip())

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

def make_link(G, node1, node2):
	if node1 not in childCount:
		childCount[node1] = 0
	childCount[node1] += 1
	gcds[node1] = -1
	gcds[node2] = -1
	if node2 not in childCount:
		childCount[node2] = 0
	childCount[node2] += 1
	if node1 not in G:
		G[node1] = {}
	G[node1][node2] = 1
	if node2 not in G:
		G[node2] = {}
	G[node2][node1] = 1
	return G

def dfs(G, node, gcdOfParent):
	for c in G[node]:
		if gcds[c] == -1:
			gcds[c] = calcGcd(gcdOfParent, vs[c])
			dfs(G, c, gcds[c])
for _ in range(t):
	global childCount
	global gcds
	global G
	childCount = {}
	gcds = []
	G = {}
	n = int(input().strip())
	gcds = [-1] * (n + 2)
	for _ in range(n - 1):
		inp = list(map(int, input().strip().split()))
		make_link(G, inp[0] - 1, inp[1] - 1)
	vs = list(map(int, input().strip().split()))
	ms = list(map(int, input().strip().split()))
	gcds[0] = vs[0]
	dfs(G, 0, gcds[0])
	nodes = [i for i in range(1, n) if childCount[i] == 1]
	nodes.sort()
	for n in nodes:
		print(ms[n] - calcGcd(ms[n], gcds[n]), end=' ')
	print()


def find_hcf(a, o):
	while o:
		(a, o) = (o, a % o)
	return a
t = int(input())
while t > 0:
	ans = []
	n = int(input())
	child = []
	parent = []
	for i in range(n + 1):
		child.append(0)
		parent.append(0)
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		if x < y:
			child[x] = y
			parent[y] = x
		else:
			child[y] = x
			parent[x] = y
	v = tuple(map(int, input().split()))
	m = tuple(map(int, input().split()))
	leaf = 0
	leaf_nodes = []
	for i in range(n, 0, -1):
		if child[i] == 0:
			leaf += 1
			leaf_nodes.append(i)
	for index in leaf_nodes:
		j = index
		p = 0
		hcf = find_hcf(v[0], m[index - 1])
		while parent[j] != 0:
			hcf = find_hcf(hcf, v[j - 1])
			p += 1
			j = parent[j]
		ans.append(m[index - 1] - hcf)
	for q in range(leaf - 1, -1, -1):
		print(ans[q], end=' ')
	t -= 1


from collections import defaultdict

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

class tree:

	def __init__(self, nodes):
		self.nodes = nodes
		self.graph = defaultdict(list)
		self.value = list()
		self.mod = list()

	def add(self, a, b):
		self.graph[a].append(b)
		self.graph[b].append(a)

	def value(self, n):
		return self.value[n - 1]

	def mvalue(self, n):
		return self.mod[n - 1]

	def start(self):
		answer = defaultdict()
		root = 1
		visited = [False for i in range(self.nodes)]
		val = self.value[0]
		visited[0] = True
		for keys in self.graph[1]:
			if visited[keys - 1] == False:
				self.dfs(keys, answer, val, visited)
		return answer

	def dfs(self, root, answer, val, visited):
		visited[root - 1] = True
		if len(self.graph[root]) == 1:
			m = self.mod[root - 1]
			v = self.value[root - 1]
			g = gcd(val, v)
			g1 = gcd(g, m)
			answer[root] = m - g1
		else:
			xx = gcd(val, self.value[root - 1])
			for i in self.graph[root]:
				if visited[i - 1] == False:
					self.dfs(i, answer, xx, visited)
for _ in range(int(input())):
	n = int(input())
	g = tree(n)
	for kk in range(n - 1):
		(a, b) = map(int, input().split())
		g.add(a, b)
	g.value = [int(i) for i in input().split()]
	g.mod = [int(i) for i in input().split()]
	ans = g.start()
	for i in range(1, n + 1):
		if i in ans:
			print(ans[i], end=' ')
	print()


from collections import defaultdict
from math import gcd
T = int(input())
for t in range(T):
	N = int(input().strip())
	tree = [[] for i in range(N)]
	for i in range(N - 1):
		(x, y) = [int(k) - 1 for k in input().strip().split()]
		tree[x].append(y)
		tree[y].append(x)
	v = [int(k) for k in input().strip().split()]
	m = [int(k) for k in input().strip().split()]
	queue = [(0, None, v[0])]
	answ = []
	while len(queue) > 0:
		(node, parent, curr_gcd) = queue.pop()
		if len(tree[node]) == 1 and node != 0:
			answ.append((node, gcd(curr_gcd, m[node])))
		else:
			for child in tree[node]:
				if child != parent:
					queue.append((child, node, gcd(curr_gcd, v[child])))
	answ.sort()
	print(' '.join((str(m[a[0]] - a[1]) for a in answ)))


from collections import defaultdict, deque
from math import gcd
for t in range(int(input())):
	(n, edges) = (int(input()), defaultdict(list))
	for _ in range(1, n):
		(x, y) = (int(i) - 1 for i in input().split())
		edges[x].append(y)
		edges[y].append(x)
	v = [int(i) for i in input().split()]
	m = [int(i) for i in input().split()]
	(queue, count) = (deque([0]), defaultdict(int, {0: 1}))
	while queue:
		i = queue.popleft()
		for j in edges[i]:
			count[j] += 1
			if count[j] > 1:
				continue
			v[j] = gcd(v[i], v[j])
			queue.append(j)
	print(*(m[i] - gcd(v[i], m[i]) for i in range(n) if count[i] == 1))


from collections import defaultdict
from sys import stdin, stdout

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

class Graph:

	def __init__(self):
		self.graph = defaultdict(list)

	def addEdge(self, u, v):
		self.graph[u].append(v)
		self.graph[v].append(u)

def iterate(g, node, hcf=0, parent=-1):
	hcf = gcd(hcf, va[node])
	if len(g.graph[node]) != 1 or node == 0:
		res[node] = -1
	else:
		res[node] = m[node] - gcd(hcf, m[node])
	for i in g.graph[node]:
		if i != parent:
			iterate(g, i, hcf, node)
t = int(stdin.readline())
while t:
	n = int(stdin.readline())
	g = Graph()
	for _ in range(n - 1):
		(u, v) = map(int, stdin.readline().split())
		u = u - 1
		v = v - 1
		g.addEdge(u, v)
	res = [-1 for _ in range(n)]
	va = list(map(int, stdin.readline().split()))
	m = list(map(int, stdin.readline().split()))
	iterate(g, 0)
	ans = ''
	for i in res:
		if i != -1:
			ans += str(i) + ' '
	print(ans)
	t = t - 1


from math import gcd
t = int(input())
for _ in range(t):
	n = int(input())
	adj = [[] for x in range(n)]
	for i in range(n - 1):
		(u, v) = map(int, input().strip().split())
		adj[u - 1].append(v - 1)
		adj[v - 1].append(u - 1)
	v = list(map(int, input().strip().split()))
	m = list(map(int, input().strip().split()))
	factors = [0] * n
	leaves = []
	parent = [-1] * n
	queue = [0]
	for i in queue:
		children = set(adj[i]) - set([parent[i]])
		if parent[i] == -1:
			factors[i] = v[i]
		else:
			factors[i] = gcd(factors[parent[i]], v[i])
		if len(children) <= 0:
			leaves.append(i)
		for q in children:
			parent[q] = i
			queue.append(q)
	leaves.sort()
	re = [m[i] - gcd(m[i], factors[i]) for i in leaves]
	print(*re)


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

def solve(l, ms, vs, leafs, u, ant, gcdAcum):
	if len(l[u]) == 1 and l[u][0] == ant:
		leafs[u] = ms[u] - gcd(gcdAcum, ms[u])
		return
	for e in l[u]:
		if e != ant:
			solve(l, ms, vs, leafs, e, u, gcd(gcdAcum, vs[e]))
t = int(input())
for _ in range(t):
	n = int(input())
	l = [[] for i in range(n)]
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		x -= 1
		y -= 1
		l[x].append(y)
		l[y].append(x)
	vs = [int(e) for e in input().split()]
	ms = [int(e) for e in input().split()]
	leafs = dict()
	solve(l, ms, vs, leafs, 0, -1, vs[0])
	for i in sorted(leafs):
		print(leafs[i], end=' ')


GI = lambda : int(input())
GIS = lambda : map(int, input().split())
LGIS = lambda : list(GIS())
from fractions import gcd
import sys
sys.setrecursionlimit(10 ** 5)

def main():
	for t in range(GI()):
		N = GI()
		edges = {}
		for _ in range(N - 1):
			(x, y) = GIS()
			for (a, b) in ((x, y), (y, x)):
				edges.setdefault(a, []).append(b)
		vs = LGIS()
		ms = LGIS()
		print(' '.join(map(str, solve(N, edges, vs, ms))))

def solve(N, edges, vs, ms):
	ret = []
	visited = [0] * N

	def recurse(i, rgcd):
		visited[i] = 1
		rgcd = gcd(rgcd, vs[i])
		gone_visiting = False
		for ii in edges[i + 1]:
			if not visited[ii - 1]:
				gone_visiting = True
				recurse(ii - 1, rgcd)
		if not gone_visiting:
			ret.append((i, ms[i] - gcd(ms[i], rgcd)))
	recurse(0, vs[0])
	return [mm for (_, mm) in sorted(ret)]
main()


from collections import defaultdict
import math
gcd_map = dict()

def get_gcd(a, b):
	if a in gcd_map:
		if b in gcd_map[a]:
			return gcd_map[a][b]
	curr_gcd = int(math.gcd(a, b))
	if a in gcd_map:
		gcd_map[a][b] = curr_gcd
	else:
		gcd_map[a] = dict()
		gcd_map[a][b] = curr_gcd
	if b in gcd_map:
		gcd_map[b][a] = curr_gcd
	else:
		gcd_map[b] = dict()
		gcd_map[b][a] = curr_gcd
	return curr_gcd

class Graph:

	def __init__(self):
		self.graph = defaultdict(lambda : list())

	def add_edge(self, u, v):
		self.graph[u].append(v)
		self.graph[v].append(u)

	def DFS(self, vs):
		m = len(self.graph)
		leaves = dict()
		root_to_node_path_gcd = [0 for _ in range(m)]
		root_to_node_path_gcd[0] = vs[0]
		stack = list()
		visited = [False for _ in range(m)]
		visited[0] = True
		stack.append(0)
		while len(stack):
			top_vertex = stack[-1]
			neighbor = None
			for i in self.graph[top_vertex]:
				if not visited[i]:
					neighbor = i
					break
			if neighbor is not None:
				visited[neighbor] = True
				stack.append(neighbor)
				root_to_node_path_gcd[neighbor] = math.gcd(root_to_node_path_gcd[top_vertex], vs[neighbor])
			else:
				if len(self.graph[top_vertex]) == 1 and top_vertex != 0:
					leaves[top_vertex] = True
				stack.pop()
		return (leaves, root_to_node_path_gcd)
for _ in range(int(input())):
	n = int(input())
	g = Graph()
	for _ in range(n - 1):
		(ui, vi) = list(map(int, input().split()))
		g.add_edge(ui - 1, vi - 1)
	vs = list(map(int, input().split()))
	ms = list(map(int, input().split()))
	(leaves, root_to_node_path_gcd) = g.DFS(vs)
	for (idx, curr_gcd) in enumerate(root_to_node_path_gcd):
		if idx in leaves:
			print(ms[idx] - math.gcd(ms[idx], curr_gcd), end=' ')


import sys
sys.setrecursionlimit(100001)
global val, mi, res

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

def dfs(n, p, x):
	s = gcd(val[n], x)
	leaf = True
	for i in adj[n]:
		if i != p:
			leaf = False
			dfs(i, n, s)
	if leaf:
		s = gcd(s, mi[n])
		if s == 1:
			res.add((n, mi[n] - 1))
		else:
			s = (mi[n] - 1) // s * s
			res.add((n, s))
t = int(input())
for _ in range(t):
	n = int(input())
	adj = [[] for _ in range(n)]
	for i in range(n - 1):
		(a, b) = [int(x) for x in input().split()]
		(a, b) = (a - 1, b - 1)
		adj[a].append(b)
		adj[b].append(a)
	val = [int(x) for x in input().split()]
	mi = [int(x) for x in input().split()]
	res = set()
	dfs(0, 0, val[0])
	for i in sorted(res):
		print(i[1], end=' ')
	print('')


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

def solve(u):
	if visited[u] == 1:
		return
	visited[u] = 1
	if len(V[u]) == 1:
		if u != 1:
			l2.append(u)
	values2[u] = gcd(values2[u], values2[pa[u]])
	for i in range(len(V[u])):
		if visited[V[u][i]] != 1:
			pa[V[u][i]] = u
			solve(V[u][i])
for _ in range(int(input())):
	n = int(input())
	V = []
	for p in range(n + 1):
		V.append([])
	for _ in range(n - 1):
		(a, b) = list(map(int, input().split()))
		V[a].append(b)
		V[b].append(a)
	values = list(map(int, input().split()))
	m = list(map(int, input().split()))
	values = [0] + values
	m = [0] + m
	visited = [0] * (n + 1)
	pa = [0] * (n + 1)
	l2 = []
	pa[1] = 1
	values2 = values[:]
	solve(1)
	l2.sort()
	for j in l2:
		mo = m[j]
		z = gcd(mo, values2[j])
		print(mo - z, end=' ')
	print()


def dfs(u):
	if visited[u] == 1:
		return
	visited[u] = 1
	if len(V[u]) == 1 and u != 1:
		leaf.append(u)
	for i in range(len(V[u])):
		if visited[V[u][i]] != 1:
			parent[V[u][i]] = u
			dfs(V[u][i])

def dfs2(u):
	if visited[u] == 1:
		return
	visited[u] = 1
	v2[u] = gcd(v2[u], v2[parent[u]])
	if len(V[u]) == 1 and u != 1:
		leaf.append(u)
	for i in range(len(V[u])):
		if visited[V[u][i]] != 1:
			parent[V[u][i]] = u
			dfs2(V[u][i])

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for _ in range(int(input())):
	n = int(input())
	V = [[] for j in range(n + 1)]
	for _ in range(n - 1):
		(x, y) = list(map(int, input().split()))
		V[x].append(y)
		V[y].append(x)
	v = list(map(int, input().split()))
	m = list(map(int, input().split()))
	v = [0] + v
	v2 = v[:]
	m = [0] + m
	visited = [0] * (n + 1)
	parent = [0] * (n + 1)
	leaf = []
	parent[1] = 1
	dfs2(1)
	leaf.sort()
	for j in leaf:
		mo = m[j]
		print(mo - gcd(mo, v2[j]), end=' ')
	print()


import sys
import math
from collections import defaultdict
sys.setrecursionlimit(100000)

def doIt(node, g, ans, p=-1):
	if node != 0 and len(adj[node]) == 1:
		ans[node] = m[node] - math.gcd(g, m[node])
		return ans
	for neigh in adj[node]:
		if neigh != p:
			ans = doIt(neigh, math.gcd(g, v[neigh]), ans, node)
	return ans
for _ in range(int(input())):
	n = int(input())
	adj = defaultdict(list)
	for _ in range(n - 1):
		(u, v) = map(lambda x: int(x) - 1, input().split())
		adj[u].append(v)
		adj[v].append(u)
	v = list(map(int, input().split()))
	m = list(map(int, input().split()))
	ans = defaultdict(lambda : -1)
	ans = doIt(0, v[0], ans)
	for i in range(n):
		if ans[i] != -1:
			print(ans[i], end=' ')


import collections
from collections import defaultdict
import math

class Graph:

	def __init__(self, n):
		self.graph = defaultdict(list)
		self.n = n

	def addEdge(self, a, b):
		self.graph[a].append(b)
		self.graph[b].append(a)

	def calculate(self, v, val, m):
		Stack = collections.deque([])
		Stack.append(v)
		visited = [False] * n
		visited[v] = True
		score = [-1] * n
		score[v] = val[v]
		ls = []
		gs = []
		temp = -1
		while len(Stack) > 0:
			flag = 0
			if len(self.graph[Stack[-1]]) == 1 and Stack[-1] != 0:
				X = Stack.pop()
				temp = math.gcd(score[X], m[X])
				ls.append(X)
				gs.append(m[X] - temp)
			else:
				Par = Stack[-1]
			for i in self.graph[Par]:
				if visited[i] == False:
					flag = 1
					last = Stack[-1]
					Stack.append(i)
					visited[i] = True
					score[i] = math.gcd(score[last], val[i])
					break
			if flag == 0:
				X = Stack.pop()
		return (ls, gs)
t = int(input())
while t:
	t -= 1
	n = int(input())
	g = Graph(n)
	for i in range(1, n):
		(u, v) = [int(x) for x in input().split()]
		g.addEdge(u - 1, v - 1)
	val = [int(x) for x in input().split()]
	m = [int(x) for x in input().split()]
	(a, b) = g.calculate(0, val, m)
	(list1, list2) = zip(*sorted(zip(a, b)))
	for i in list2:
		print(i, end=' ')
	print()


from math import gcd
for _ in range(int(input())):
	n = int(input())
	b = [[] for i in range(n)]
	vis = [0] * n
	for i in range(n - 1):
		(c, d) = map(int, input().split())
		b[c - 1].append(d - 1)
		b[d - 1].append(c - 1)
	st = [0]
	v = list(map(int, input().split()))
	m = list(map(int, input().split()))
	while st:
		x = st.pop()
		vis[x] = 1
		for i in b[x]:
			if vis[i] == 0:
				st.append(i)
				v[i] = gcd(v[i], v[x])
	le = []
	for i in range(1, n):
		if len(b[i]) == 1:
			le.append(i)
	a = []
	for i in le:
		a.append(m[i] - gcd(m[i], v[i]))
	print(*a)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	g = [[] for i in range(n)]
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		x -= 1
		y -= 1
		g[x].append(y)
		g[y].append(x)
	a = list(map(int, input().split()))
	m = list(map(int, input().split()))
	ans = [a[i] for i in range(n)]
	vis = [0] * n
	vis[0] = 1
	st = []
	st.append(0)
	tmp = []
	while len(st):
		x = st[-1]
		st.pop()
		for i in g[x]:
			if not vis[i]:
				if len(g[i]) == 1:
					tmp.append(i)
				vis[i] = 1
				ans[i] = gcd(ans[x], a[i])
				st.append(i)
	tmp.sort()
	for i in tmp:
		print(m[i] - gcd(m[i], ans[i]), end=' ')
	print()


import math
cases = int(input())
while cases > 0:
	n = int(input())
	visited = [False] * n
	graph = [[] for x in range(n)]
	for i in range(n - 1):
		(x, y) = input().split()
		x = int(x) - 1
		y = int(y) - 1
		graph[x].append(y)
		graph[y].append(x)
	v = list(map(int, input().split()))
	m = list(map(int, input().split()))
	gcds = [0] * n
	gcds[0] = v[0]
	visited[0] = True
	queue = [0]
	leaves = []
	while len(queue) != 0:
		x = queue.pop()
		for y in graph[x]:
			if not visited[y]:
				visited[y] = True
				gcds[y] = math.gcd(gcds[x], v[y])
				queue.append(y)
		if x != 0 and len(graph[x]) == 1:
			leaves.append(x)
	leaves.sort()
	for i in leaves:
		p = gcds[i]
		q = m[i]
		print(str(q - math.gcd(p, q)), end=' ')
	print('', end='\n')
	cases -= 1


import sys
sys.setrecursionlimit(100010)
T = int(input())

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

def compute_the_max_remainders_for_all_the_leaves_of_the_tree(tree, V, M, is_node_visited, max_remainders_list, curr_node, curr_gcd):
	is_node_visited[curr_node] = True
	curr_gcd = compute_gcd(curr_gcd, V[curr_node])
	if curr_node != 0 and len(tree[curr_node]) == 1:
		curr_gcd = compute_gcd(curr_gcd, M[curr_node])
		max_remainder = M[curr_node] - curr_gcd
		max_remainders_list.append((curr_node, max_remainder))
	else:
		for child in tree[curr_node]:
			if is_node_visited[child] == False:
				compute_the_max_remainders_for_all_the_leaves_of_the_tree(tree, V, M, is_node_visited, max_remainders_list, child, curr_gcd)
while T:
	N = int(input())
	tree = [[] for _ in range(N)]
	for _ in range(N - 1):
		(u, v) = list(map(int, input().split()))
		tree[u - 1].append(v - 1)
		tree[v - 1].append(u - 1)
	V = list(map(int, input().split()))
	M = list(map(int, input().split()))
	is_node_visited = [False for _ in range(N)]
	max_remainders_list = []
	compute_the_max_remainders_for_all_the_leaves_of_the_tree(tree, V, M, is_node_visited, max_remainders_list, 0, V[0])
	max_remainders_list.sort()
	for i in range(len(max_remainders_list)):
		print(max_remainders_list[i][1], end=' ')
	print()
	T -= 1


import math
for i in range(int(input())):
	n = int(input())
	d1 = {}
	d2 = {}
	for i in range(0, n - 1):
		(x, y) = map(int, input().split())
		if x not in d1:
			d1[x] = [y]
		else:
			d1[x].append(y)
		if y not in d1:
			d1[y] = [x]
		else:
			d1[y].append(x)
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	ans = []
	l3 = [0] * n
	visited = {}
	queue = [1]
	while len(visited) != n:
		s = queue.pop()
		if s not in visited:
			visited[s] = 1
			for item in d1[s]:
				if item not in visited:
					l1[item - 1] = math.gcd(l1[item - 1], l1[s - 1])
					queue.append(item)
	for i in range(2, n + 1):
		if len(d1[i]) == 1:
			f = l2[i - 1] - math.gcd(l1[i - 1], l2[i - 1])
			print(f, end=' ')
	print('')


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

def dfs(node, par, curgcd):
	if len(g[node]) == 1 and g[node][0] == par:
		gcd = gcdf(A[node], curgcd)
		ans[node] = m[node] - gcdf(gcd, m[node])
	else:
		gcd = gcdf(curgcd, A[node])
		for i in g[node]:
			if i == par:
				continue
			dfs(i, node, gcdf(gcd, A[i]))
T = int(input())
for t in range(T):
	n = int(input())
	g = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v) = [int(i) for i in input().split()]
		u -= 1
		v -= 1
		g[u].append(v)
		g[v].append(u)
	A = [int(i) for i in input().split()]
	m = [int(i) for i in input().split()]
	gcd = A[0]
	ans = [-1 for i in range(n)]
	dfs(0, -1, A[0])
	fin = []
	for i in ans:
		if i != -1:
			fin.append(i)
	print(*fin)


from collections import deque

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for _ in range(int(input())):
	n = int(input())
	a = [[] for _ in range(n + 1)]
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		a[x].append(y)
		a[y].append(x)
	v = list(map(int, input().split()))
	m = list(map(int, input().split()))
	vis = [0] * (n + 1)
	q = deque([1])
	val = [v[0]] * (n + 1)
	e = [[] for _ in range(n + 1)]
	vis[1] = 1
	while q:
		p = q.popleft()
		for i in a[p]:
			if vis[i] == 0:
				e[p].append(i)
				vis[i] = 1
				q.append(i)
				val[i - 1] = gcd(v[i - 1], val[p - 1])
	for i in range(1, n + 1):
		if len(e[i]) == 0:
			print(m[i - 1] - gcd(val[i - 1], m[i - 1]), end=' ')


import sys
sys.setrecursionlimit(100000)

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

def dfs(no, visit, d, values, module, ans, an):
	visit[no] = 1
	f = 0
	for i in d[no]:
		if visit[i] == 0:
			f = 1
			dfs(i, visit, d, values, module, ans, gcd(an, values[i - 1]))
	if f == 0:
		ans.append([no, module[no - 1] - gcd(an, module[no - 1])])
t = int(input())
for _ in range(t):
	n = int(input())
	d = dict()
	ans = []
	visit = [0] * (n + 1)
	for i in range(1, n + 1):
		d[i] = []
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		d[u].append(v)
		d[v].append(u)
	values = list(map(int, input().split()))
	module = list(map(int, input().split()))
	dfs(1, visit, d, values, module, ans, values[0])
	ans.sort()
	for i in range(len(ans)):
		print(ans[i][1], end=' ')
	print()


import math
for _ in range(int(input())):
	n = int(input())
	dic = {'1': 1}
	graph = [[] for i in range(n + 1)]
	myMom = [0 for x in range(n + 1)]
	score = []
	mykey = 0
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		graph[a].append(b)
		graph[b].append(a)
	value = list(map(int, input().split()))
	value.insert(0, 0)
	mod = list(map(int, input().split()))
	mod.insert(0, 0)

	def run(nodeNum):
		c = 0
		for v in graph[nodeNum]:
			if str(v) not in dic.keys():
				c += 1
				myMom[v] = nodeNum
				dic[str(v)] = 1
				run(v)
		if c == 0:
			gcd = math.gcd(mod[nodeNum], value[nodeNum])
			backward = myMom[nodeNum]
			while backward != 0 and gcd != 1:
				gcd = math.gcd(value[backward], gcd)
				backward = myMom[backward]
			score.append([nodeNum, mod[nodeNum] - gcd])
	run(1)
	score.sort()
	for (_, l_ans) in score:
		print(l_ans, end=' ')
	print()


from math import gcd
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	tree = {}
	for i in range(1, n):
		(x, y) = list(map(int, input().strip().split()))
		x -= 1
		y -= 1
		tree[x] = tree.get(x, []) + [y]
		tree[y] = tree.get(y, []) + [x]
	v = list(map(int, input().strip().split()))
	m = list(map(int, input().strip().split()))
	visited = {}
	ans = []

	def solve(curr, g):
		visited[curr] = True
		if len(tree[curr]) == 1 and curr != 0:
			ans.append((curr, m[curr] - gcd(g, m[curr])))
			return
		for node in tree[curr]:
			if node not in visited:
				solve(node, gcd(v[node], g))
	solve(0, v[0])
	for x in sorted(ans):
		print(x[1], end=' ')


from collections import defaultdict
import sys
sys.setrecursionlimit(100000)

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

def read_line(mentioned_type=int):
	return tuple(map(mentioned_type, input().split()))

def dfs(node, values, m, graph, visited, ans, val=None):
	visited.add(node)
	if val:
		val = gcd(val, values[node - 1])
	else:
		val = values[node - 1]
	is_leaf = True
	for each in graph[node]:
		if each not in visited:
			is_leaf = False
			dfs(each, values, m, graph, visited, ans, val)
	if is_leaf:
		ans[node] = m[node - 1] - gcd(val, m[node - 1])
t = int(input())
while t:
	n = int(input())
	graph = defaultdict(set)
	for i in range(n - 1):
		(u, v) = read_line()
		graph[u].add(v)
		graph[v].add(u)
	values = read_line()
	m = read_line()
	ans = {}
	dfs(1, values, m, graph, set(), ans)
	print(' '.join(map(lambda x: str(x[1]), sorted(ans.items()))))
	t -= 1


from math import gcd

def listgcd(List):
	min(List)
for _ in range(int(input())):
	N = int(input())
	ans = []
	Tree = {}
	Tree[1] = None
	Tree_path = {1: [1]}
	for _ in range(N - 1):
		(x, y) = map(int, input().split())
		if x in Tree:
			Tree[y] = x
			Tree_path[y] = Tree_path[x] + [y]
		else:
			Tree[x] = y
			Tree_path[x] = Tree_path[y] + [x]
	Leaf = sorted(set(Tree.keys()) - set(Tree.values()))
	values = dict(((i + 1, j) for (i, j) in enumerate(map(int, input().split()))))
	module = dict(((i + 1, j) for (i, j) in enumerate(map(int, input().split()))))
	for i in Leaf:
		mod = module[i]
		t = mod
		for j in Tree_path[i]:
			t = gcd(t, values[j])
			if t == 1:
				ans.append(mod - 1)
				break
		else:
			ans.append(mod - t)
	print(*ans, sep=' ')


from collections import defaultdict

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

class Graph:

	def __init__(self):
		self.graph = defaultdict(list)
		self.parents = None
		self.leafs = None

	def add_edge(self, u, v):
		self.graph[u].append(v)
		self.graph[v].append(u)

	def bfs(self, s, vals, gcds):
		visited = [False] * len(self.graph)
		self.leafs = []
		self.parents = [None] * len(self.graph)
		queue = []
		queue.append(s)
		visited[s] = True
		gcds[0] = vals[0]
		while queue:
			s = queue.pop(0)
			leaf = True
			for i in self.graph[s]:
				if visited[i] == False:
					gcds[i] = gcd(gcds[s], vals[i])
					self.parents[i] = s
					leaf = False
					queue.append(i)
					visited[i] = True
			if leaf:
				self.leafs.append(s)
t = int(input())
for _t in range(t):
	n = int(input())
	g = Graph()
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		g.add_edge(u - 1, v - 1)
	values = list(map(int, input().split()))
	param = list(map(int, input().split()))
	gcds = [None] * n
	g.bfs(0, values, gcds)
	g.leafs.sort()
	for l in g.leafs:
		print(param[l] - gcd(gcds[l], param[l]), end=' ')


from math import gcd
import bisect
import itertools
import sys
from collections import deque
I = lambda : sys.stdin.readline()
mod = 10 ** 9 + 7

def modu(a, m):
	if a % m:
		return a % m
	return m

def mindiff(a):
	b = a[:]
	b.sort()
	m = 10000000000
	for i in range(len(b) - 1):
		if b[i + 1] - b[i] < m:
			m = b[i + 1] - b[i]
	return m

def lcm(a, b):
	return a * b // gcd(a, b)

def merge(a, b):
	i = 0
	j = 0
	c = 0
	ans = []
	while i < len(a) and j < len(b):
		if a[i] < b[j]:
			ans.append(a[i])
			i += 1
		else:
			ans.append(b[j])
			c += len(a) - i
			j += 1
	ans += a[i:]
	ans += b[j:]
	return (ans, c)

def mergesort(a):
	if len(a) == 1:
		return (a, 0)
	mid = len(a) // 2
	(left, left_inversion) = mergesort(a[:mid])
	(right, right_inversion) = mergesort(a[mid:])
	(m, c) = merge(left, right)
	c += left_inversion + right_inversion
	return (m, c)

def is_prime(num):
	if num == 1:
		return False
	if num == 2:
		return True
	if num == 3:
		return True
	if num % 2 == 0:
		return False
	if num % 3 == 0:
		return False
	t = 5
	a = 2
	while t <= int(math.sqrt(num)):
		if num % t == 0:
			return False
		t += a
		a = 6 - a
	return True

def ceil(a, b):
	if a % b == 0:
		return a // b
	else:
		return a // b + 1

def ncr1(n, r):
	s = 1
	for i in range(min(n - r, r)):
		s *= n - i
		s %= mod
		s *= pow(i + 1, mod - 2, mod)
		s %= mod
	return s

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x

def check(a, b, c):
	for i in range(0, c - 1):
		if a * i % b == c:
			return i
	return 0
for _ in range(int(input())):
	n = int(input())
	a = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		a[x].append(y)
		a[y].append(x)
	q = deque([1])
	v = [0] + list(map(int, input().split()))
	m = [0] + list(map(int, input().split()))
	e = [[] for i in range(n + 1)]
	p = [1] * (n + 1)
	val = v[:]
	vis = [0] * (n + 1)
	vis[1] = 1
	while q:
		k = q.popleft()
		for i in a[k]:
			if vis[i] == 0:
				e[k].append(i)
				vis[i] = 1
				val[i] = gcd(val[k], v[i])
				q.append(i)
				p[i] = k
	for i in range(1, n + 1):
		if len(e[i]) == 0:
			print(m[i] - gcd(m[i], val[i]), end=' ')
	print()


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def maketree(graph, root, V):
	(leaves, gcdnode) = ([], {})
	visited = set([])
	heap = [(root, V[root])]
	while heap:
		(u, value) = heap.pop(0)
		visited.add(u)
		gcdnode[u] = gcd(V[u], value)
		leave = True
		for v in graph[u]:
			if v not in visited:
				leave = False
				heap.append((v, gcdnode[u]))
		if leave:
			leaves.append(u)
	return (sorted(leaves), gcdnode)

def solve(N, V, M, graph):
	(leaves, gcdnode) = maketree(graph, 1, V)
	solution = [M[leave] - gcd(gcdnode[leave], M[leave]) for leave in leaves]
	return solution
T = int(input().strip())
for problem in range(1, T + 1):
	N = int(input().strip())
	graph = {}
	for u in range(1, N + 1):
		graph[u] = []
	for i in range(N - 1):
		(u, v) = list(map(int, input().strip().split()))
		graph[u].append(v)
		graph[v].append(u)
	V = [0] + list(map(int, input().strip().split()))
	M = [0] + list(map(int, input().strip().split()))
	print(' '.join(map(str, solve(N, V, M, graph))))


t = int(input())
import math

def dfs(i, tree, p, gout, arr):
	gins = math.gcd(gout, v[i - 1])
	if len(tree[i]) == 1 and tree[i][0] == p:
		arr.append([i, m[i - 1] - math.gcd(gins, m[i - 1])])
	else:
		for k in tree[i]:
			if k != p:
				dfs(k, tree, i, gins, arr)
for _ in range(t):
	n = int(input())
	tree = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		tree[u].append(v)
		tree[v].append(u)
	v = list(map(int, input().split()))
	m = list(map(int, input().split()))
	arr = []
	dfs(1, tree, -1, v[0], arr)
	a = ''
	arr.sort()
	for i in arr:
		a += str(i[1]) + ' '
	print(a[:-1])


from collections import defaultdict
from math import gcd
from sys import stdin, setrecursionlimit
setrecursionlimit = 10 ** 6

def calc(p, x, m):
	Sum = sum(p)
	d = gcd(x, m)
	if Sum == 0 or m == 0:
		return 0
	r = Sum % d
	for y in p:
		if not y % d:
			continue
		r = max(r, y % d)
		r = max(r, (Sum - y) % d)
		r = max(r, calc(p - {y}, y, d) % d)
	return r

def dfs(tree, parent, node, par):
	stack = []
	visited = [0] * (len(tree) + 1)
	stack.append((node, par))
	while stack:
		(node, par) = stack.pop()
		if visited[node]:
			continue
		visited[node] = 1
		parent[node] = par
		for v in tree[node]:
			if v != par:
				stack.append((v, node))

def dfs_recc(tree, parent, node, par):
	parent[node] = par
	for v in tree[node]:
		if v != par:
			dfs_recc(tree, parent, v, node)

def get_path(parent, V, node, mod):
	path = set()
	for x in (0, node):
		if V[x] % mod:
			path.add(V[x] % mod)
	while node != 0:
		if V[node] % mod:
			path.add(V[node] % mod)
		node = parent[node]
	return path

def solve():
	for _ in range(int(stdin.readline())):
		N = int(stdin.readline())
		tree = defaultdict(list)
		parent = [-1] * N
		for _ in range(N - 1):
			(u, v) = map(int, stdin.readline().split())
			tree[u - 1].append(v - 1)
			tree[v - 1].append(u - 1)
		dfs_recc(tree, parent, 0, -1)
		V = [int(k) for k in stdin.readline().split()]
		M = [int(k) for k in stdin.readline().split()]
		result = []
		for node in range(1, N):
			if len(tree[node]) < 2:
				mod = M[node]
				path = get_path(parent, V, node, mod)
				ans = 0
				d = mod
				for x in path:
					d = gcd(d, x)
				ans = max(ans, mod - d)
				result.append(ans)
		print(' '.join((str(k) for k in result)))
solve()


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

def simplify(G, i):
	q = []
	leaves = []
	par = {1: 0}
	q.append(i)
	while len(q) > 0:
		c = q[0]
		for x in G[c]:
			del G[x][G[x].index(c)]
			par[x] = c
			if len(G[x]) > 0:
				q.append(x)
			else:
				leaves.append(x)
		del q[0]
	return [leaves, par]

def solve(leaf, par, V, m):
	c = leaf
	f = m
	x = f
	while c > 0:
		x = gcd(V[c], x)
		if x < f:
			f = x
		if f == 1:
			break
		c = par[c]
	return m - f
for tc in range(int(input())):
	N = int(input())
	G = {i: [] for i in range(1, N + 1)}
	for i in range(N - 1):
		[u, v] = [int(x) for x in input().split()]
		G[u].append(v)
		G[v].append(u)
	V = [0] + [int(x) for x in input().split()]
	M = [0] + [int(x) for x in input().split()]
	[leaves, par] = simplify(G, 1)
	leaves.sort()
	ans = []
	for leaf in leaves:
		ans.append(solve(leaf, par, V, M[leaf]))
	print(' '.join([str(x) for x in ans]))


from collections import deque

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

def gcd(l):
	res = l[0]
	for c in l[1:]:
		res = hcf(res, c)
	return res
t = int(input())
for tc in range(t):
	res = []
	n = int(input())
	tree = []
	for i in range(n):
		tree.append([])
	for nn in range(n - 1):
		xy = input().split()
		x = int(xy[0])
		y = int(xy[1])
		tree[x - 1].append(y - 1)
		tree[y - 1].append(x - 1)
	v = [int(i) for i in input().split()]
	m = [int(i) for i in input().split()]
	q = deque()
	q.append(0)
	h = [0] * n
	h[0] = v[0]
	visited = [0] * n
	visited[0] = 1
	while len(q) > 0:
		ver = q.popleft()
		for i in tree[ver]:
			if visited[i] == 0:
				q.append(i)
				visited[i] = 1
				h[i] = hcf(h[ver], v[i])
	for i in range(1, n):
		x = tree[i]
		if len(x) == 1:
			ans = m[i] - hcf(h[i], m[i])
			res.append(ans)
	print(*res)


import math

def Solve(graph, values, mods):
	n = len(values)
	gcds = [0] * n
	visited = [False] * n
	stack = [1]
	while stack:
		node = stack.pop()
		if not visited[node - 1]:
			visited[node - 1] = True
			gcds[node - 1] = math.gcd(gcds[node - 1], values[node - 1])
			for kid in graph[node]:
				if not visited[kid - 1]:
					gcds[kid - 1] = math.gcd(gcds[node - 1], gcds[kid - 1])
					stack.append(kid)
	leaves = []
	for i in graph.keys():
		if len(graph[i]) == 1 and i != 1:
			leaves.append(i)
	leaves.sort()
	ans = ''
	for leaf in leaves:
		g = math.gcd(gcds[leaf - 1], mods[leaf - 1])
		gcds[leaf - 1] = g
		if g > 1:
			ans += str(mods[leaf - 1] - g) + ' '
		else:
			ans += str(mods[leaf - 1] // g - 1) + ' '
	print(ans)

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		graph = {}
		for j in range(1, n + 1):
			graph[j] = []
		for j in range(n - 1):
			(x, y) = map(int, input().split())
			graph[x].append(y)
			graph[y].append(x)
		values = list(map(int, input().split()))
		mods = list(map(int, input().split()))
		Solve(graph, values, mods)
main()


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
from collections import defaultdict
from collections import deque
for _ in range(int(input())):
	n = int(input())
	d = defaultdict(list)
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		d[u].append(v)
		d[v].append(u)
	v = [0] + list(map(int, input().split()))
	m = [0] + list(map(int, input().split()))
	b = deque()
	b.append(1)
	parent = [0] * (n + 1)
	while len(b) != 0:
		t = b.popleft()
		for i in d[t]:
			if parent[t] != i:
				v[i] = gcd(v[i], v[t])
				parent[i] = t
				b.append(i)
	for i in range(2, n + 1):
		if len(d[i]) == 1:
			mod = m[i]
			t = v[i]
			print(mod - gcd(t, mod), end=' ')


import resource, sys
resource.setrlimit(resource.RLIMIT_STACK, (2 ** 29, -1))
sys.setrecursionlimit(10 ** 6)
from math import gcd

def input():
	return sys.stdin.readline().strip()

def dfs(node, p):
	leaf = True
	for to in graph[node]:
		if to == p:
			continue
		leaf = False
		v[to] = gcd(v[to], v[node])
		dfs(to, node)
	if leaf == True:
		leaves.append(node)

def main():
	for _ in range(int(input())):
		global n, graph, v, m, leaves
		n = int(input())
		graph = [[] for i in range(n + 1)]
		for i in range(n - 1):
			(x, y) = map(int, input().split())
			graph[x].append(y)
			graph[y].append(x)
		v = list(map(int, input().split()))
		v.insert(0, 0)
		m = list(map(int, input().split()))
		m.insert(0, 0)
		leaves = []
		dfs(1, 1)
		leaves.sort()
		ans = []
		for i in leaves:
			x = gcd(v[i], m[i])
			ans.append(m[i] - x)
		print(*ans)
main()


def directify(graph, root=0):
	front = [root]
	while len(front) > 0:
		parent = front.pop()
		kids = graph[parent]
		front.extend(kids)
		for kid in kids:
			g_kids = graph[kid]
			found = False
			for (index, g_kid) in enumerate(g_kids):
				if g_kid == parent:
					found = True
					break
			if found:
				(g_kids[index], g_kids[-1]) = (g_kids[-1], g_kids[index])
				g_kids.pop()

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

def scores(graph, values, mods, root=0):
	to_visit = [(root, values[root])]
	leaves = []
	while len(to_visit) > 0:
		(cur, parent_gcd) = to_visit.pop()
		kids = graph[cur]
		cur_gcd = gcd(parent_gcd, values[cur])
		to_visit.extend([(kid, cur_gcd) for kid in kids])
		if len(kids) == 0:
			cur_mod = mods[cur]
			leaf_gcd = gcd(cur_gcd, cur_mod)
			score = cur_mod - leaf_gcd
			leaves.append((cur, score))
	leaves.sort()
	ret = [val for (_, val) in leaves]
	return ret
for _ in range(int(input())):
	N = int(input())
	graph = [[] for _ in range(N)]
	for _ in range(N - 1):
		(a, b) = map(lambda x: int(x) - 1, input().split())
		graph[a].append(b)
		graph[b].append(a)
	graph_vals = list(map(int, input().split()))
	graph_mods = list(map(int, input().split()))
	directify(graph)
	ret = scores(graph, graph_vals, graph_mods)
	print(' '.join(map(str, ret)))


from sys import *
import os
import re
from math import *

def nextline():
	return list(map(lambda x: int(x.strip()), input().strip().split()))
T = int(input())
setrecursionlimit(200000)
ans = []
g = []

def solve(u, p, m):
	isleaf = True
	m = gcd(m, V[u])
	for v in g[u]:
		if v == p:
			continue
		isleaf = False
		solve(v, u, m)
	if isleaf:
		mod = M[u]
		m = gcd(m, mod)
		ans[u] = mod - m
for t in range(T):
	N = int(input())
	ans = [-1] * N
	g = [[] for x in range(N)]
	for i in range(N - 1):
		(u, v) = nextline()
		u -= 1
		v -= 1
		g[u].append(v)
		g[v].append(u)
	V = nextline()
	M = nextline()
	solve(0, -1, 0)
	print(*[x for x in ans if x != -1])


import math

def getAnswers(adj, value, modulus, node, parent, answer):
	if parent != -1:
		value[node] = math.gcd(value[node], value[parent])
	for v in adj[node]:
		if v != parent:
			getAnswers(adj, value, modulus, v, node, answer)
	if len(adj[node]) == 1 and parent != -1:
		answer[node] = modulus[node] - math.gcd(modulus[node], value[node])
t = int(input())
for _ in range(t):
	n = int(input())
	adj = [[] for _ in range(n)]
	answer = [-1] * n
	for _ in range(n - 1):
		(a, b) = [int(x) for x in input().split()]
		adj[a - 1].append(b - 1)
		adj[b - 1].append(a - 1)
	value = [int(x) for x in input().split()]
	modulus = [int(x) for x in input().split()]
	getAnswers(adj, value, modulus, 0, -1, answer)
	print(' '.join([str(x) for x in answer if x != -1]))