*“Animal instinct. When faced with danger, seek refuge in the herd.”*

Jun-Ho has come to know about the escape passage route that VIPs use in case of emergency. Jun-Ho is in the leader's office and he is planning his escape from the building.

The building has a tree-like structure, with the leader's office as the root. Jun-Ho has obtained information on this structure, in the form of a tree on N nodes rooted at 1. The building has some security, which can be calculated as follows:

Each node of the tree has a value assigned to it — say, A_{i} for node i.
Let u be a leaf node of the tree. The security of u is defined to be the bitwise OR of all values on the (unique) path from the root to u. Let this value be denoted L_{u}.
The security of the tree is then defined to be the sum of the security of all its leaf nodes, i.e, the sum of L_{u} across all leaf nodes u of the tree.

The tree is considered to be *secure* when L_{u} > 0 for every leaf node u of the tree; otherwise it is said to be *insecure*.

Jun-Ho would like the security of the tree to be as low as possible when making his escape. To this end, he can perform the following operation zero or more times:
Pick a node 1 ≤ u ≤ N of the tree, and set A_{u} = 0.

However, if the tree ever becomes insecure as a result of an operation, the leader is immediately alerted and will foil Jun-Ho's plan. Thus, Jun-Ho cannot perform an operation that would make the tree insecure.

Help Jun-Ho find the minimum possible security the tree can have, such that the tree remains secure after every operation.

Note: 
A leaf is a node of the tree without any child nodes.
For N = 1, the root is also considered to be a leaf.
Given input tree will be secured tree.

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

- The first line of 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, denoting the number of nodes of the tree.
- The next N-1 lines each contain two space-separated integers u and v, denoting an edge between nodes u and v in the tree.
- The next line contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N} — the values of the nodes.

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

For each test case, output a single integer denoting the minimum security of the tree.

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

$1 ≤ T ≤ 10^{3}$
$1 ≤ N ≤ 10^{6}$
$0 ≤ A_{i} ≤ 10^{9}$
$1 ≤ u,v ≤ N$
- The graph given in the input will always be a secured tree
- Sum of $N$ over all test cases does not exceed $10^{6}$.

----- Sample Input 1 ------ 
3
1
5
5
1 2
1 3
3 4
3 5
5 2 3 1 4
4
1 2
1 3
1 4
2 2 2 2
----- Sample Output 1 ------ 
5
7
6
----- explanation 1 ------ 
Test Case 1: No operation can be done, and the minimum security of the tree is thus $5$.

Test Case 2: Set $A_{1}$ and $A_{3}$ to $0$. It can be seen that $L_{2} = 2$, $L_{4} = 1$ and $L_{5} = 4$; so every leaf  has positive security. The security of the tree is $2 + 1 + 4 = 7$, and this is the minimum attainable.

Test Case 3: The given tree already has minimum security, that being $6$.

Source: codechef | Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal


Solutions:
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)
P = -123123123

def solve(u=0, p=P):
	if len(g[u]) == 1:
		if a[u] == 0:
			return (float('inf'), 1)
		return (a[u], 1)
	s = l = 0
	for v in g[u]:
		if v != p:
			(x, y) = solve(v, u)
			s += x
			l += y
	if a[u] == 0:
		return (s, l)
	return (min(s, a[u] * l), l)
for _ in range(int(input())):
	n = int(input())
	g = [[] for _ in range(n)]
	g[0].append(P)
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		g[u - 1].append(v - 1)
		g[v - 1].append(u - 1)
	a = list(map(int, input().split()))
	if n == 1:
		print(a[0])
		continue
	print(solve()[0])