"Say my Name".
Todd Alquist is being taught the process of cooking methamphetamine, but to see whether he's really capable of learning it, Walt gives him a problem to solve. Since he can't solve it, he asks you for help.
You are given a tree with $N$ vertices (numbered $1$ through $N$), rooted at the vertex $1$. There is an integer written at each vertex; for each valid $i$, the value of vertex $i$ is $A$$i$.There also exists a special integer $K$. 
Choose any leaf node, denoted by $X$, and go down a simple path from $root$ to $X$.
Let $S$ denote the set of all nodes lying on the simple path from $root$ to $X$.
For all $ i $ $\epsilon $ $ S $, choose an integer $D$ $\epsilon$ $[2^{A[i]-1},2^{A[i]})$.

Informally, for every node $i$ lying on the simple path from $root$ to $X$, you have to choose an integer $D$ such that  $2^{A[i]-1}\leq D < 2^{A[i]}$.  
You now have to perform one of the two following operations :   
- Bitwise XOR of all chosen integers.  
- Bitwise AND of all chosen integers.   
You have to determine whether you can choose the values in such a way that after performing one of the given operations you can get an integer equal to $K$.  
- Note : A leaf is a node of the tree without any child nodes.
Determine if it is possible to obtain the value $K$ by performing the given operations.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- First line of each testcase contains two space separated integers $N, K$ denoting the number of nodes and the value of the special integer .
- $N-1$ lines follow , each line contains two space separated integers $u,v$ denoting an edge between $u$ and $v$. 
- A single line follows containing $N$ space separated integers denoting the value of nodes.

-----Output:-----
For each testcase, output in a single line "YES"(without quotes) or "NO"(without quotes).

-----Constraints-----
- $1 \leq T \leq 10000$
- $2 \leq N \leq 5*10^5$
- $1 \leq K \leq 10^{18}$
- $1 \leq u,v \leq N$
- $ 1\leq A[i] \leq 64$
- Sum of $N$ over all test cases does not exceed 1e6.

-----Sample Input:-----
1
6 85
1 2
2 3
2 4
4 5
3 6
3 5 4 7 1 9

-----Sample Output:-----
YES

-----EXPLANATION:-----
There are two leaf nodes, 5 and 6
considering path from root to 5
we have nodes
1->2->4->5
we can select the values
5,26,75,1 and perform operation 1 that is XOR of all numbers to get 85

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

Graph algorithms

Graph traversal

Tree algorithms

Mathematics

Data structures


Solutions:
import sys
import math
from collections import defaultdict, Counter
import threading
input = sys.stdin.readline

def print(x):
	sys.stdout.write(str(x) + '\n')
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

@bootstrap
def find(u, g, e, g2, e2, le):
	visit[u - 1] = 1
	if a[u - 1] > g:
		g = a[u - 1]
		e = 1
	elif a[u - 1] == g:
		e += 1
	if a[u - 1] < g2:
		g2 = a[u - 1]
		e2 = 1
	elif a[u - 1] == g2:
		e2 += 1
	for j in l[u]:
		if visit[j - 1] == 0:
			flag = (yield find(j, g, e, g2, e2, le))
			if flag:
				yield 1
		elif len(l[u]) == 1:
			if g == le and e & 1 or (g > le and e % 2 == 0) or g2 == le or (g2 > le and g > g2):
				yield 1
	yield 0

def add(a, b):
	l[a].append(b)
	l[b].append(a)
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = defaultdict(list)
	for j in range(n - 1):
		(u, v) = map(int, input().split())
		add(u, v)
	a = list(map(int, input().split()))
	visit = [0] * n
	le = len(bin(k)) - 2
	if find(1, 0, 0, 100, 0, le):
		print('YES')
	else:
		print('NO')
sys.setrecursionlimit(10 ** 5)


t = int(input())
for _ in range(t):
	(n, k) = [int(j) for j in input().split()]
	for pow_k in range(64):
		if k == 0:
			break
		k = k // 2
	edges = [[0] * 2 for _ in range(n - 1)]
	for i in range(n - 1):
		edges[i] = [int(j) - 1 for j in input().split()]
	numbers = [int(j) for j in input().split()]
	vertex_set = [[] for _ in range(n)]
	for i in range(n - 1):
		vertex_set[edges[i][0]].append(edges[i][1])
		vertex_set[edges[i][1]].append(edges[i][0])
	vertices = [0]
	parent = dict()
	parent[0] = -1
	for i in range(n):
		vertex = vertices[i]
		for v in vertex_set[vertex]:
			if v != parent[vertex]:
				vertices.append(v)
				parent[v] = vertex
	and_op = [0 for _ in range(n)]
	xor_op = [0 for _ in range(n)]
	leaf_node = [True for _ in range(n)]
	if numbers[0] >= pow_k:
		and_op[0] = numbers[0]
	xor_op[0] = numbers[0]
	for i in range(1, n):
		vertex = vertices[i]
		parent_vertex = parent[vertex]
		if numbers[vertex] >= pow_k and and_op[parent_vertex] >= pow_k:
			if numbers[vertex] != and_op[parent_vertex]:
				and_op[vertex] = pow_k
			else:
				and_op[vertex] = and_op[parent_vertex]
		if numbers[vertex] == xor_op[parent_vertex] % 100:
			if xor_op[parent_vertex] < 100:
				xor_op[vertex] = xor_op[parent_vertex] + 100
			else:
				xor_op[vertex] = numbers[vertex]
		elif numbers[vertex] > xor_op[parent_vertex] % 100:
			xor_op[vertex] = numbers[vertex]
		else:
			xor_op[vertex] = xor_op[parent_vertex]
		leaf_node[parent_vertex] = False
	success = False
	for vertex in vertices:
		if leaf_node[vertex]:
			if and_op[vertex] == pow_k:
				success = True
				break
			if xor_op[vertex] % 100 > pow_k and xor_op[vertex] > 100 or xor_op[vertex] == pow_k:
				success = True
				break
	if success:
		print('YES')
	else:
		print('NO')


import sys, collections
input = sys.stdin.readline

def main1():
	T = int(input())
	for _ in range(T):
		(N, K) = map(int, input().split())
		Tree = {}
		for j in range(N):
			Tree[j] = []
		for i in range(N - 1):
			(u, v) = map(int, input().split())
			Tree[u - 1].append(v - 1)
			Tree[v - 1].append(u - 1)
		A = list(map(int, input().split()))
		vis = [0 for i in range(N)]
		maxval = [[0, 0] for i in range(N)]
		minval = [0 for i in range(N)]
		lfnode = []
		vis[0] = 1
		Q = collections.deque([0])
		(maxval[0][0], maxval[0][1]) = (A[0], 1)
		minval[0] = A[0]
		while len(Q) != 0:
			a = Q.pop()
			mv1 = maxval[a][0]
			mv2 = minval[a]
			flag = 0
			for i in Tree[a]:
				if vis[i] == 0:
					vis[i] = 1
					flag = 1
					v = A[i]
					Q.append(i)
					if mv1 < v:
						(maxval[i][0], maxval[i][1]) = (v, 1)
					elif mv1 == v:
						(maxval[i][0], maxval[i][1]) = (mv1, maxval[a][1] + 1)
					else:
						(maxval[i][0], maxval[i][1]) = (maxval[a][0], maxval[a][1])
					if mv2 > v:
						minval[i] = v
					elif v == mv2:
						minval[i] = mv2
					else:
						minval[i] = minval[a]
			if flag == 0:
				lfnode.append(a)
		flag = 0
		K1 = len(bin(K)) - 2
		for i in lfnode:
			(v1, v2) = (maxval[i][0], maxval[i][1])
			if v1 > K1 and v2 % 2 == 0:
				flag = 1
			elif v1 == K1 and v2 % 2 == 1:
				flag = 1
			v11 = minval[i]
			if v11 > K1 and v11 != v1:
				flag = 1
			elif v11 == K1:
				flag = 1
			if flag == 1:
				break
		if flag == 1:
			print('YES')
		else:
			print('NO')
main1()