Due to the rise of covid-19 cases in India, this year BCCI decided to organize knock-out matches in IPL rather than a league. 
Today is matchday 3 and it is between Geek's favorite team Royal Challengers Banglore and the most powerful batting team - Sunrisers Hyderabad. Virat Kholi captain of the team RCB tried everything to win the trophy but never succeeded. He went to guruji to seek the blessing, but the guruji gave him a problem and asked him to solve it. Guruji gave him a tree-like structure, asked him to stand at the target node and find the sum of all nodes within a maximum distance of k from the target node. can Kholi solve this problem to qualify for the next round?
Note: The target node should be included in the sum. 
Example 1:
Input:
                   1
                 /    \
                2      9
               /      /  \
              4      5     7
            /   \         /  \
           8     19     20    11
          /     /  \
         30   40   50
target = 9, K = 1
Output:
22
Explanation:
Nodes within distance 1 from 9 are 9, 5, 7, 1  
Example 2:
Input:
                   1
                 /    \
                2      9
               /      /  \
              4      5     7
            /   \         /  \
           8     19     20    11
          /     /  \
         30   40   50
target = 40, K = 2
Output:
113
Explanation:
Nodes within distance 2 from 40 are 40, 19, 50, 4
Your Task:
You don't need to read input or print anything. Complete the function sum_at_distK() which takes the root of the tree, target, and K  as input parameter and returns the sum of all nodes within a max distance of k from the target 
Constraints:
1 ≤ N, Node Value ≤ 10^{5}
1 ≤ K ≤ 20

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: '''

# node class:



class Node:

    def __init__(self, val):

        self.right = None

        self.data = val

        self.left = None



'''



class Solution:

    def sum_at_distK(self, root, target, k):

        # Your code goes here





Solutions:
class Solution:

	def solve2(self, p, k):
		if not p:
			return
		if k > 0:
			self.ans += p.data
			self.solve2(p.left, k - 1)
			self.solve2(p.right, k - 1)

	def solve(self, p, target, k):
		if not p:
			return (0, -1)
		if p.data == target:
			self.ans += p.data
			self.solve2(p.left, k)
			self.solve2(p.right, k)
			return (1, k)
		left = self.solve(p.left, target, k)
		if left[0] == 1:
			if left[1] > 0:
				self.ans += p.data
				self.solve2(p.right, left[1] - 1)
			return (1, left[1] - 1)
		right = self.solve(p.right, target, k)
		if right[0] == 1:
			if right[1] > 0:
				self.ans += p.data
				self.solve2(p.left, right[1] - 1)
			return (1, right[1] - 1)
		return (0, -1)

	def sum_at_distK(self, root, target, k):
		self.ans = 0
		self.solve(root, target, k)
		return self.ans


class Solution:

	def makeparent(self, root, target):
		if root.data == target:
			self.node = root
		if root.left:
			self.parent[root.left] = root
			self.makeparent(root.left)
		if root.right:
			self.parent[root.right] = root
			self.makeparent(root.right)

	def makeparent(self, root, target):
		q = deque()
		q.append(root)
		while q:
			top = q.popleft()
			if top.data == target:
				self.node = top
			if top.left:
				self.parent[top.left] = top
				q.append(top.left)
			if top.right:
				self.parent[top.right] = top
				q.append(top.right)

	def sum_at_distK(self, root, target, k):
		self.parent = {root: None}
		self.node = None
		count = 0
		visited = set()
		self.makeparent(root, target)
		q = deque()
		q.append([self.node, 0])
		while q:
			(top, val) = q.popleft()
			visited.add(top)
			if val <= k:
				count += top.data
			if top.left and val < k and (top.left not in visited):
				q.append([top.left, val + 1])
			if top.right and val < k and (top.right not in visited):
				q.append([top.right, val + 1])
			if self.parent[top] and val < k and (self.parent[top] not in visited):
				q.append([self.parent[top], val + 1])
		return count


class Solution:

	def sum_at_distK(self, root, target, k):
		target_path = ''
		stack = [(root, '')]
		while stack:
			(node, path) = stack.pop()
			if node is None:
				continue
			if node.data == target:
				target_path = path
				break
			stack.append((node.left, path + 'l'))
			stack.append((node.right, path + 'r'))
		summa = 0
		stack = [(root, target_path, k)]
		while stack:
			(node, path, k) = stack.pop()
			if not node or k <= 0:
				continue
			if node.data == target:
				k += 1
			if path and path[0] == 'l':
				stack.append((node.left, path[1:], k))
				stack.append((node.right, '', k - len(path)))
			elif path and path[0] == 'r':
				stack.append((node.right, path[1:], k))
				stack.append((node.left, '', k - len(path)))
			else:
				stack.append((node.left, '', k - 1))
				stack.append((node.right, '', k - 1))
			if k - len(path) >= 0:
				summa += node.data
		return summa


from collections import deque

class Solution:

	def fin_nod(self, root, target):
		if root is None:
			return None
		if root.data == target:
			return root
		lh = self.fin_nod(root.left, target)
		rh = self.fin_nod(root.right, target)
		if lh:
			return lh
		return rh

	def sum_at_distK(self, root, target, k):
		par = {root: -1}
		q = deque()
		q.append(root)
		while q:
			nod = q.popleft()
			if nod.left:
				par[nod.left] = nod
				q.append(nod.left)
			if nod.right:
				par[nod.right] = nod
				q.append(nod.right)
		nod = self.fin_nod(root, target)
		q = deque()
		q.append([nod, 0])
		sumi = 0
		vis = set([nod, None, -1])
		while q:
			(nod, dis) = q.popleft()
			sumi += nod.data
			for i in [nod.left, nod.right, par[nod]]:
				if i not in vis and dis + 1 <= k:
					q.append([i, dis + 1])
					vis.add(i)
		return sumi


class Solution:

	def find_parent(self, root, parent, targ, node):
		if root == None:
			return None
		if root.data == targ:
			node[0] = root
		l = self.find_parent(root.left, parent, targ, node)
		r = self.find_parent(root.right, parent, targ, node)
		if l != None:
			parent[l] = root
		if r != None:
			parent[r] = root
		return root

	def find_ele(self, root, parent, k, ans, dis, visited):
		if root == None or visited[root]:
			return
		if dis <= k:
			ans[0] += root.data
		visited[root] = True
		self.find_ele(root.left, parent, k, ans, dis + 1, visited)
		self.find_ele(root.right, parent, k, ans, dis + 1, visited)
		self.find_ele(parent[root], parent, k, ans, dis + 1, visited)

	def sum_at_distK(self, root, target, k):
		parent = {root: None}
		node = [None]
		ans = [0]
		visited = {}
		self.find_parent(root, parent, target, node)
		for i in parent:
			visited[i] = False
		self.find_ele(node[0], parent, k, ans, 0, visited)
		return ans[0]
from collections import deque

class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		line = input()
		root = buildTree(line)
		line = input().strip().split()
		target = int(line[0])
		k = int(line[1])
		obj = Solution()
		print(obj.sum_at_distK(root, target, k))


class Solution:

	def fillUpNodes(self, root, neighbours):
		if root.left:
			neighbours[root.data].add(root.left)
			if root.left.data in neighbours:
				neighbours[root.left.data].add(root)
			else:
				neighbours[root.left.data] = set([root])
		if root.right:
			neighbours[root.data].add(root.right)
			if root.right.data in neighbours:
				neighbours[root.right.data].add(root)
			else:
				neighbours[root.right.data] = set([root])

	def dfs(self, root, visited, neighbours, k, totalSum):
		if not root or root in visited or k < 0:
			return
		visited.add(root)
		totalSum[0] += root.data
		for node in neighbours[root.data]:
			self.dfs(node, visited, neighbours, k - 1, totalSum)

	def fillNeighbours(self, root, neighbours, start):
		if not root:
			return
		self.fillNeighbours(root.left, neighbours, start)
		if target == root.data and (not start[0]):
			start[0] = root
		if root.data in neighbours:
			self.fillUpNodes(root, neighbours)
		else:
			neighbours[root.data] = set()
			self.fillUpNodes(root, neighbours)
		self.fillNeighbours(root.right, neighbours, start)

	def sum_at_distK(self, root, target, k):
		neighbours = dict()
		start = [None]
		self.fillNeighbours(root, neighbours, start)
		totalSum = [0]
		self.dfs(start[0], set(), neighbours, k, totalSum)
		return totalSum[0]


class Solution:

	def sum_at_distK(self, root, target, k):
		q = []
		q.append(root)
		mp = dict()
		ans = None
		while len(q) > 0:
			c = q.pop(0)
			if c.data == target:
				ans = c
			if c.left:
				q.append(c.left)
				mp[c.left] = c
			if c.right:
				q.append(c.right)
				mp[c.right] = c
		q = []
		vis = dict()
		vis[ans] = True
		q.append(ans)
		i = 0
		mp[root] = None
		s = 0
		while len(q) > 0:
			if i == k + 1:
				break
			i += 1
			for i1 in range(len(q)):
				c = q.pop(0)
				s = s + c.data
				(left, right, up) = (c.left, c.right, mp[c])
				if left:
					if left not in vis:
						vis[left] = True
						q.append(left)
				if right:
					if right not in vis:
						vis[right] = True
						q.append(right)
				if up:
					if up not in vis:
						vis[up] = True
						q.append(up)
		return s


from collections import defaultdict

class Solution:

	def sum_at_distK(self, root, target, k):
		d = defaultdict(list)

		def helper(root):
			if root is None:
				return
			if root.left:
				d[root.data].append(root.left.data)
				d[root.left.data].append(root.data)
				helper(root.left)
			if root.right:
				d[root.data].append(root.right.data)
				d[root.right.data].append(root.data)
				helper(root.right)
		helper(root)
		if target not in d:
			return -1
		sm = 0
		visited = {}

		def dfs(node, level):
			nonlocal k, visited, sm, d
			if level > k:
				return
			if node not in visited:
				sm = sm + node
			visited[node] = True
			for i in d[node]:
				dfs(i, level + 1)
		dfs(target, 0)
		return sm


class Solution:

	def sum_at_distK(self, root, target, k):
		ans = 0

		def getSumTillK(root, level):
			if root is None or level > k:
				return 0
			if level == k:
				return root.data
			return root.data + getSumTillK(root.left, level + 1) + getSumTillK(root.right, level + 1)

		def util(root):
			nonlocal ans
			if root is None:
				return
			if root.data == target:
				ans += getSumTillK(root, 0)
				return 0
			l = util(root.left)
			if l is not None:
				if l + 1 > k:
					return float('inf')
				else:
					ans += root.data + getSumTillK(root.right, l + 2)
					return l + 1
			r = util(root.right)
			if r is not None:
				if r + 1 > k:
					return float('inf')
				else:
					ans += root.data + getSumTillK(root.left, r + 2)
					return r + 1
		util(root)
		return ans


class Solution:

	def sum_at_distK(self, root, target, k):
		if root is None:
			return 0

		def findSum(root, k):
			if root is None or k < 0:
				return 0
			return root.data + findSum(root.left, k - 1) + findSum(root.right, k - 1)

		def helper(root, target, k):
			if root is None:
				return (0, -1)
			if root.data == target:
				sm = findSum(root, k)
				return (sm, k - 1)
			(sm, dist) = helper(root.left, target, k)
			if sm > 0:
				if dist == -1:
					return (sm, dist)
				sm = sm + findSum(root.right, dist - 1) + root.data
				return (sm, dist - 1)
			(sm, dist) = helper(root.right, target, k)
			if sm > 0:
				if dist == -1:
					return (sm, dist)
				sm = sm + findSum(root.left, dist - 1) + root.data
				return (sm, dist - 1)
			return (0, -1)
		(sm, dist) = helper(root, target, k)
		return sm


class Solution:

	def sum_at_distK(self, root, target, k):
		if root is None:
			return 0
		targetNode = []

		def createGraph(root):
			if root is None:
				return
			if root.data == target:
				targetNode.append(root)
			if root.left:
				root.left.parent = root
			if root.right:
				root.right.parent = root
			createGraph(root.left)
			createGraph(root.right)
		createGraph(root)
		if not targetNode:
			return 0
		target = targetNode[0]
		seen = set()
		level = 0
		q = [target]
		res = 0
		while q:
			temp = []
			while q:
				node = q.pop(0)
				if node in seen:
					continue
				seen.add(node)
				res += node.data
				if node.left:
					temp.append(node.left)
				if node.right:
					temp.append(node.right)
				if 'parent' in dir(node) and node.parent:
					temp.append(node.parent)
			if level == k:
				return res
			level += 1
			q = temp
		return res


class Solution:

	def findNode_and_fillparent_and_visited(self, root, parent, d, target):
		global node
		if not root:
			return
		d[root] = [parent, False]
		if root.data == target:
			node = root
		self.findNode_and_fillparent_and_visited(root.left, root, d, target)
		self.findNode_and_fillparent_and_visited(root.right, root, d, target)

	def findsum(self, root, k, d):
		if not root:
			return 0
		if d[root][1]:
			return 0
		else:
			d[root][1] = True
		if k == 0:
			return root.data
		return root.data + self.findsum(root.left, k - 1, d) + self.findsum(root.right, k - 1, d) + self.findsum(d[root][0], k - 1, d)

	def sum_at_distK(self, root, target, k):
		global node
		node = None
		d = {}
		self.findNode_and_fillparent_and_visited(root, None, d, target)
		return self.findsum(node, k, d)


class Solution:

	def sum_at_distK(self, root, target, k):
		res = [0]
		traverse(root, target, k, res)
		return res[0]

def traverse(cur, target, k, res):
	if not cur:
		return -1
	left_dist = traverse(cur.left, target, k, res)
	right_dist = traverse(cur.right, target, k, res)
	dist = -1
	if cur.data == target:
		dist = 0
		get_node(cur.left, k - 1, res)
		get_node(cur.right, k - 1, res)
	elif left_dist != -1:
		dist = left_dist + 1
		if k > dist:
			get_node(cur.right, k - dist - 1, res)
	elif right_dist != -1:
		dist = right_dist + 1
		if k > dist:
			get_node(cur.left, k - dist - 1, res)
	if dist != -1 and dist <= k:
		res[0] += cur.data
	return dist

def get_node(cur, k, res):
	if not cur:
		return
	if k >= 0:
		res[0] += cur.data
		get_node(cur.left, k - 1, res)
		get_node(cur.right, k - 1, res)