Chef and his mother are going travelling. Chef's world consists of $N$ cities (numbered $1$ through $N$) connected by $N-1$ bidirectional roads such that each city can be reached from any other city using roads. For each city, we know its age — the number of years elapsed since the foundation of the city; let's denote the age of city $i$ by $a_i$.
First of all, Chef and his mother have to decide what city they should visit first. Suppose that Chef chooses a city $c_c$ and his mother chooses a (not necessarily different) city $c_m$. The difference of their choices is the number of different bits in the binary representations of $a_{c_c}$ and $a_{c_m}$.
Chef will not argue with his mother if the parity of this difference is not equal to the parity of the length of the shortest path between cities $c_c$ and $c_m$ (the number of roads on the shortest path between them). Find the number of ways to choose the cities $c_c$ and $c_m$ such that Chef avoids quarreling with his mother.

-----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 $A$ and $B$ denoting a road between cities $A$ and $B$.
- The last line contains $N$ space-separated integers $a_1, a_2, \dots, a_N$.

-----Output-----
For each test case, print a single line containing one integer — the number of valid pairs $c_c, c_m$.

-----Constraints-----
- $1 \le T \le 10$
- $1 \le N \le 10^5$
- $1 \le A, B \le N$
- $0 \le a_i \le 10^9$ for each valid $i$

-----Sample Input-----
1
3
1 2
1 3
1 2 3

-----Sample Output-----
2

-----Explanation-----
Example case 1: The two possible choices are $c_c=2, c_m=3$ (their binary representations differ by one bit, the shortest path has length $2$) and $c_c=1, c_m=2$ (there are two different bits in their binary representations and the shortest path has length $1$).

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation


Solutions:
import sys
sys.setrecursionlimit(10 ** 6)
for t in range(int(input())):
	N = int(input())
	g = [[] for i in range(N + 1)]
	for i in range(N - 1):
		(u, v) = map(int, input().split())
		g[u].append(v)
		g[v].append(u)
	A = [None] + [bin(int(Ai)).count('1') % 2 for Ai in input().split()]
	cnt = [0] * 4

	def dfs(u, p, d):
		cnt[A[u] << 1 | d] += 1
		for v in g[u]:
			if v != p:
				dfs(v, u, d ^ 1)
	dfs(1, 1, 0)
	ans = 0
	for m in range(16):
		(p0, p1, d0, d1) = (m & 1, m >> 1 & 1, m >> 2 & 1, m >> 3 & 1)
		if p0 ^ p1 ^ d0 ^ d1:
			ans += cnt[p0 << 1 | d0] * cnt[p1 << 1 | d1]
	print(ans // 2)


import sys
sys.setrecursionlimit(10 ** 6)
for t in range(int(input())):
	N = int(input())
	g = [[] for i in range(N + 1)]
	for i in range(N - 1):
		(u, v) = map(int, input().split())
		g[u].append(v)
		g[v].append(u)
	A = [None] + [bin(int(Ai)).count('1') % 2 for Ai in input().split()]
	cnt = [[0, 0], [0, 0]]

	def dfs(u, p, d):
		cnt[A[u]][d] += 1
		for v in g[u]:
			if v != p:
				dfs(v, u, d ^ 1)
	dfs(1, 1, 0)
	ans = (cnt[0][0] + cnt[1][1]) * (cnt[0][1] + cnt[1][0])
	print(ans)


import sys
sys.setrecursionlimit(1000000)
for _ in range(eval(input())):
	C = []
	n = eval(input())
	for i in range(n):
		C.append([])
	for i in range(n - 1):
		(a, b) = [int(x) - 1 for x in input().split()]
		C[a].append(b)
		C[b].append(a)
	cnt = 0
	Co = [bin(int(x)).count('1') for x in input().split()]
	Q = [0] * (n + 100)
	cur = 0
	done = [0] * n
	done[0] = 1
	H = [0] * n
	for i in range(n):
		r = Q[i]
		if H[r] & 1 == Co[r] & 1:
			cnt += 1
		for i in C[r]:
			if done[i] == 0:
				done[i] = 1
				Q[cur + 1] = i
				cur += 1
				H[i] = H[r] + 1
	print(cnt * (n - cnt))