You are given a [tree] with N nodes rooted at node 1.  
The i^{th} node of the tree has a value A_{i} assigned to it. 

For the i^{th} node (1≤ i ≤ N), output the minimum value of [bitwise XOR] of the values of any two distinct nodes in the subtree of node i.

Formally, for each node i, find the value of min(A_{x} \oplus A_{y}), where x \ne y and x, y \in  subtree of node i.  
Note that since leaf nodes have only 1 node in their subtree, output -1 for all the leaf nodes.

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

- First line will contain T, number of test cases. Then the test cases follow.
- Each test case begins with a single line of input, an integer N - the number of nodes in the tree.
- The following (N-1) lines each contain two integers, U and V, denoting an undirected edge between nodes U and V.
- The last line of each test case contains N integers. The i^{th} integer is the value assigned to i^{th} node.

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

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

For each test case, output N integers where the i^{th} integer is the minimum value of [bitwise XOR] of the values of any two distinct nodes in the subtree of node i.  
If node i is a leaf node, output -1 instead.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ U, V≤ N$ and $U\ne V$
$0 ≤ A_{i} ≤ 10^{15}$ 
- It is guaranteed that the edges given in the input form a tree. 
- Sum of $N$ over all test cases does not exceed $10^{5}$.

----- Sample Input 1 ------ 
2
1
10
3
1 2
1 3
4 5 6
----- Sample Output 1 ------ 
-1
1 -1 -1

----- explanation 1 ------ 
Test case $1$: There is only one node in the tree which is a leaf node. Hence, the output is $-1$.

Test case $2$: The tree formed by the input of second test case is shown below:

- Nodes $2$ and Node $3$ are leaf nodes. Hence, the answer for them is $-1$. 
- For the subtree formed by node $1$, the answer is $min((4\oplus5),(5\oplus6), (4\oplus6))$ which is $min(1, 3, 2) = 1$.

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

Graph algorithms

String algorithms

Tree algorithms

Mathematics

Spanning trees

Data structures


Solutions:
from collections import deque
from enum import Enum, auto

class RedBlackTree:

	class Colour(Enum):
		RED = auto()
		BLACK = auto()

	class Node:

		def __init__(self, key):
			self.parent = None
			self.left = None
			self.right = None
			self.colour = RedBlackTree.Colour.RED
			self.key = key

		@property
		def grandparent(self):
			return self.parent and self.parent.parent

		@property
		def sibling(self):
			p = self.parent
			return p and (p.right if p.left == self else p.left)

		@property
		def uncle(self):
			p = self.parent
			return p and p.sibling

		def has_red_child(self):
			return self.left and self.left.colour == RedBlackTree.Colour.RED or (self.right and self.right.colour == RedBlackTree.Colour.RED)

		def is_on_left(self):
			return self.parent.left == self

		def find(self, v):
			if self.key == v:
				return self
			child = self.left if self.key > v else self.right
			return child and child.find(v)

		def far_left(self):
			if self.left:
				return self.left.far_left()
			else:
				return self

		def far_right(self):
			if self.right:
				return self.right.far_right()
			else:
				return self

		def next(self):
			if self.right:
				return self.right.far_left()
			n = self
			p = n.parent
			while p:
				if n == p.left:
					return p
				n = p
				p = n.parent
			return None

		def prev(self):
			if self.left:
				return self.left.far_right()
			n = self
			p = n.parent
			while p:
				if n == p.right:
					return p
				n = p
				p = n.parent
			return None

		def __str__(self):
			return str(self.key) + ' ' + str(self.colour)

	def __init__(self):
		self.root = None
		self.len = 0

	@staticmethod
	def is_red(node):
		return node and node.colour == RedBlackTree.Colour.RED

	def rotate_left(self, n):
		nnew = n.right
		p = n.parent
		n.right = nnew.left
		nnew.left = n
		n.parent = nnew
		if n.right:
			n.right.parent = n
		if p:
			if n == p.left:
				p.left = nnew
			elif n == p.right:
				p.right = nnew
		else:
			self.root = nnew
		nnew.parent = p

	def rotate_right(self, n):
		nnew = n.left
		p = n.parent
		n.left = nnew.right
		nnew.right = n
		n.parent = nnew
		if n.left:
			n.left.parent = n
		if p:
			if n == p.left:
				p.left = nnew
			elif n == p.right:
				p.right = nnew
		else:
			self.root = nnew
		nnew.parent = p

	def insert(self, k):
		n = self.Node(k)

		def insert_recurse(root):
			if root and n.key < root.key:
				if root.left:
					insert_recurse(root.left)
					return
				else:
					root.left = n
			elif root:
				if root.right:
					insert_recurse(root.right)
					return
				else:
					root.right = n
			n.parent = root

		def repair_insert(n):
			if not n.parent:
				n.colour = RedBlackTree.Colour.BLACK
			elif n.parent.colour == RedBlackTree.Colour.BLACK:
				return
			elif n.uncle and n.uncle.colour == RedBlackTree.Colour.RED:
				n.parent.colour = RedBlackTree.Colour.BLACK
				n.uncle.colour = RedBlackTree.Colour.BLACK
				n.grandparent.colour = RedBlackTree.Colour.RED
				repair_insert(n.grandparent)
			else:
				p = n.parent
				g = n.grandparent
				if n == p.right and p == g.left:
					self.rotate_left(p)
					n = n.left
				elif n == p.left and p == g.right:
					self.rotate_right(p)
					n = n.right
				p = n.parent
				g = n.grandparent
				if n == p.left:
					self.rotate_right(g)
				else:
					self.rotate_left(g)
				p.colour = RedBlackTree.Colour.BLACK
				g.colour = RedBlackTree.Colour.RED
		insert_recurse(self.root)
		repair_insert(n)
		self.root = n
		while self.root.parent:
			self.root = self.root.parent
		self.len += 1

	def remove(self, v):

		def fix_double_black(n):
			if n == self.root:
				return
			p = n.parent
			s = n.sibling
			if not s:
				fix_double_black(n.parent)
				return
			if s.colour == RedBlackTree.Colour.RED:
				p.colour = RedBlackTree.Colour.RED
				s.colour = RedBlackTree.Colour.BLACK
				if p.left == n:
					self.rotate_left(p)
				else:
					self.rotate_right(p)
				fix_double_black(n)
			elif s.has_red_child():
				if self.is_red(s.left):
					if s.is_on_left():
						s.left.colour = s.colour
						s.colour = p.colour
						self.rotate_right(p)
					else:
						s.left.colour = p.colour
						self.rotate_right(s)
						self.rotate_left(p)
				elif s.is_on_left():
					s.right.colour = p.colour
					self.rotate_left(s)
					self.rotate_right(p)
				else:
					s.right.colour = s.colour
					s.colour = p.colour
					self.rotate_left(p)
				p.colour = RedBlackTree.Colour.BLACK
			else:
				s.colour = RedBlackTree.Colour.RED
				if p.colour == RedBlackTree.Colour.BLACK:
					fix_double_black(p)
				else:
					p.colour = RedBlackTree.Colour.BLACK

		def delete(n):
			child = n.left or n.right
			if not (self.is_red(n) or self.is_red(child)):
				fix_double_black(n)
			if child:
				child.parent = n.parent
				child.colour = RedBlackTree.Colour.BLACK
			if not n.parent:
				self.root = child
			elif n.is_on_left():
				n.parent.left = child
			else:
				n.parent.right = child
		n = self.root.find(v)
		if n.right and n.left:
			m = n.right.far_left()
			n.key = m.key
			n = m
		delete(n)
		self.len -= 1

	def find(self, v):
		return self.root and self.root.find(v)

	def __iter__(self):
		if not self.root:
			return None
		n = self.root.far_left()
		while n:
			yield n.key
			n = n.next()

	def __len__(self):
		return self.len

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		edges = [[int(a) for a in input().split()] for _ in range(n - 1)]
		aa = [0] + [int(a) for a in input().split()]
		res = solve(n, edges, aa)
		print(' '.join(map(str, res)))
INF = 10000000000000000

def solve(n, edges, aa):
	adj = [[] for _ in range(n + 1)]
	for (u, v) in edges:
		adj[u].append(v)
		adj[v].append(u)
	parent = [0] * (n + 1)
	dl = []
	q = deque([1])
	while q:
		v = q.popleft()
		for w in adj[v]:
			if w != parent[v]:
				dl.append(w)
				parent[w] = v
				q.append(w)
	dl.reverse()
	res = [INF] * (n + 1)
	values = [RedBlackTree() for _ in range(n + 1)]
	for (i, a) in enumerate(aa):
		values[i].insert(a)
	for u in dl:
		res[parent[u]] = min(res[parent[u]], res[u])
		if len(values[u]) > len(values[parent[u]]):
			(values[u], values[parent[u]]) = (values[parent[u]], values[u])
		for v in values[u]:
			values[parent[u]].insert(v)
			vn = values[parent[u]].find(v)
			pn = vn.prev()
			if pn:
				res[parent[u]] = min(res[parent[u]], pn.key ^ v)
			nn = vn.next()
			if nn:
				res[parent[u]] = min(res[parent[u]], nn.key ^ v)
	return [-1 if r == INF else r for r in res[1:]]
main()


from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(2 * 10 ** 5)

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

class OrderedList(SortedList):

	def __init__(self, arg):
		super().__init__(arg)

	def rangeCountByValue(self, leftVal, rightVal):
		leftCummulative = self.bisect_left(leftVal)
		rightCummulative = self.bisect_left(rightVal + 1)
		return rightCummulative - leftCummulative

def dfs(p, prev):
	total = SortedList([])
	total.add(a[p - 1])
	value = float('inf')
	for i in child[p]:
		if i == prev:
			continue
		(take, val) = dfs(i, p)
		if len(take) > len(total):
			(total, take) = (take, total)
		value = min(value, val)
		for x in take:
			ind = total.bisect_left(x)
			if ind < len(total):
				value = min(value, total[ind] ^ x)
			if ind > 0:
				value = min(value, total[ind - 1] ^ x)
			total.add(x)
	if value == float('inf'):
		ans[p - 1] = -1
	else:
		ans[p - 1] = value
	return [total, value]
for T in range(int(input())):
	n = int(input())
	child = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		child[u].append(v)
		child[v].append(u)
	a = list(map(int, input().split()))
	ans = [-1 for i in range(n)]
	dfs(1, -1)
	print(*ans)