Cupid wants to strike maximum houses in Geek Land on Valentine's Day. The houses in Geek Land are arranged in the form of a binary tree. Cupid is standing at target node initially. 
Find the sum of all nodes within a maximum distance k from target node. 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 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N, Node Value ≤ 10^{5}
1 ≤ K ≤ 20

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Range queries

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 sum_at_distK(self, root, home, k):

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

		def solve(root, home, k, ans):
			if root == None:
				return -1
			if root.data == home:
				ans[0] += findforSubtree(root, k)
				return 0
			leftDistance = solve(root.left, home, k, ans)
			rightDistance = solve(root.right, home, k, ans)
			if rightDistance != -1:
				if rightDistance + 1 <= k:
					ans[0] += root.data + findforSubtree(root.left, k - rightDistance - 2)
				return rightDistance + 1
			if leftDistance != -1:
				if leftDistance + 1 <= k:
					ans[0] += root.data + findforSubtree(root.right, k - leftDistance - 2)
				return leftDistance + 1
			return -1
		ans = [0]
		solve(root, home, k, ans)
		return ans[0]


class Solution:

	def sum_at_distK(self, root, target, k):
		path = self.findPath(root, target, '')
		return self.findSum(root, k, path, target)

	def findPath(self, root, target, path):
		if root is None:
			return ''
		if root.data == target:
			return path
		left = self.findPath(root.left, target, path + 'l')
		right = self.findPath(root.right, target, path + 'r')
		return left + right

	def findSum(self, root, k, path, target):
		if root is None or not k:
			return 0
		k += root.data == target
		if not path:
			k -= 1
			summa = root.data
			summa += self.findSum(root.left, k, path, target)
			summa += self.findSum(root.right, k, path, target)
			return summa
		n = len(path)
		if path[0] == 'l':
			if n > k:
				return self.findSum(root.left, k, path[1:], target)
			if n == k:
				return self.findSum(root.left, k, path[1:], target) + root.data
			left = self.findSum(root.left, k, path[1:], target)
			right = self.findSum(root.right, k - n, '', target)
			return left + right + root.data
		if n > k:
			return self.findSum(root.right, k, path[1:], target)
		if n == k:
			return self.findSum(root.right, k, path[1:], target) + root.data
		left = self.findSum(root.right, k, path[1:], target)
		right = self.findSum(root.left, k - n, '', target)
		return left + right + root.data


from collections import deque

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 maptoparent(self, root, target):
		q = [root]
		(pos, len1) = (0, 1)
		while pos < len1:
			top = q[pos]
			if top.data == target:
				self.node = top
			if top.left:
				q.append(top.left)
				len1 += 1
				self.parent[top.left] = top
			if top.right:
				q.append(top.right)
				len1 += 1
				self.parent[top.right] = top
			pos += 1

	def computesum(self, k):
		self.sum = self.node.data
		q = [[self.node, k]]
		(pos, len1) = (0, 1)
		visited = {self.node}
		while pos < len1:
			(node, k) = q[pos]
			print('k =', k, node.data)
			if k >= 0:
				if node.left and node.left not in visited:
					self.sum += node.left.data
					q.append([node.left, k - 1])
					len1 += 1
				if node.right and node.right not in visited:
					self.sum += node.right.data
					q.append([node.right, k - 1])
					len1 += 1
				if node in self.parent:
					parent = self.parent[node]
					if parent not in self.visited:
						self.sum += node.parent.data
						q.append([parent, k - 1])
						len1 += 1
			pos += 1
		return self.sum

	def computesum(self, root, k):
		if k < 0 or root is None:
			return
		self.sum += root.data
		self.visited.add(root)
		if root.left not in self.visited:
			self.computesum(root.left, k - 1)
		if root.right not in self.visited:
			self.computesum(root.right, k - 1)
		if root in self.parent:
			parent = self.parent[root]
		else:
			return
		if parent not in self.visited:
			self.computesum(self.parent[root], k - 1)

	def sum_at_distK(self, root, target, k):
		self.parent = {}
		self.sum = 0
		self.node = None
		self.visited = set()
		self.maptoparent(root, target)
		self.computesum(self.node, k)
		return self.sum


class Solution:

	def maptoparent(self, root):
		if root is None:
			return
		if not root.left and (not root.right):
			return
		if root.left:
			self.parent[root.left] = root
			self.maptoparent(root.left)
		if root.right:
			self.parent[root.right] = root
			self.maptoparent(root.right)

	def find(self, root, target):
		if root is None:
			return
		if self.node:
			return
		if root.data == target:
			self.node = root
		self.find(root.left, target)
		self.find(root.right, target)

	def computesum(self, root, k):
		if k < 0 or root is None:
			return
		self.sum += root.data
		self.visited.add(root)
		if root.left not in self.visited:
			self.computesum(root.left, k - 1)
		if root.right not in self.visited:
			self.computesum(root.right, k - 1)
		if root in self.parent:
			parent = self.parent[root]
		else:
			return
		if parent not in self.visited:
			self.computesum(self.parent[root], k - 1)

	def sum_at_distK(self, root, target, k):
		self.parent = {}
		self.sum = 0
		self.node = None
		self.maptoparent(root)
		self.find(root, target)
		self.visited = set()
		self.computesum(self.node, k)
		return self.sum


class Node_:

	def __init__(self, node):
		node.head = None

class Solution:

	def sum_at_distK(self, root, target, k):
		sum_ = [0]
		Node_(root)
		root.head = None
		if root.left:
			Node_(root.left)
			root.left.head = root
		if root.right:
			Node_(root.right)
			root.right.head = root
		self.sum_at_distKUtil(root, target, k, sum_)
		return sum_[0]

	def sum_at_distKUtil(self, root, target, k, sum_):
		if target == root.data:
			self.front(root, k, sum_)
			self.back(root.head, k - 1, sum_)
			return
		if root.left:
			Node_(root.left)
			root.left.head = root
			self.sum_at_distKUtil(root.left, target, k, sum_)
		if root.right:
			Node_(root.right)
			root.right.head = root
			self.sum_at_distKUtil(root.right, target, k, sum_)

	def back(self, root, k, sum_):
		if k >= 0 and root and root.data:
			sum_[0] += root.data
			root.data = 0
			self.back(root.head, k - 1, sum_)
			self.front(root.left, k - 1, sum_)
			self.front(root.right, k - 1, sum_)

	def front(self, root, k, sum_):
		if k >= 0 and root and root.data:
			sum_[0] += root.data
			root.data = 0
			self.front(root.left, k - 1, sum_)
			self.front(root.right, k - 1, sum_)


from collections import defaultdict

class Solution:

	def sum_at_distK(self, root, target, k):
		graph = defaultdict(lambda : [])

		def dfs(root):
			if root:
				if root.left:
					graph[root.data].append(root.left.data)
					graph[root.left.data].append(root.data)
					dfs(root.left)
				if root.right:
					graph[root.data].append(root.right.data)
					graph[root.right.data].append(root.data)
					dfs(root.right)
		dfs(root)
		(q, visited, res) = ([target], set(), 0)
		for _ in range(k + 1):
			tmp = []
			for node in q:
				if node in visited:
					continue
				visited.add(node)
				res += node
				for dst in graph[node]:
					tmp.append(dst)
			q = tmp
		return res


from collections import deque

class Solution:

	def sum_at_distK(self, root, target, k):
		p = dict()
		q = deque()
		q.append(root)
		x = None
		while len(q) > 0:
			curr = q.popleft()
			if curr.data == target:
				x = curr
			if curr.left != None:
				p[curr.left] = curr
				q.append(curr.left)
			if curr.right != None:
				p[curr.right] = curr
				q.append(curr.right)
		d = dict()
		q.clear()
		q.append(x)
		d[x] = 1
		ans = 0
		i = 0
		while len(q):
			if i > k:
				break
			i += 1
			n = len(q)
			for j in range(n):
				root = q.popleft()
				ans += root.data
				if root.left != None and root.left not in d:
					q.append(root.left)
					d[root.left] = 1
				if root.right != None and root.right not in d:
					q.append(root.right)
					d[root.right] = 1
				if root in p and p[root] not in d:
					q.append(p[root])
					d[p[root]] = 1
		return ans


from collections import deque, defaultdict

class Solution:

	def sum_at_distK(self, root, target, k):
		parentLookup = defaultdict()
		queue = deque()
		queue.append([root, None])
		targetNode = None
		while queue:
			currQueueLen = len(queue)
			for _ in range(currQueueLen):
				(currNode, currNodeParent) = queue.popleft()
				if currNode.data == target:
					targetNode = currNode
				parentLookup[currNode.data] = currNodeParent
				if currNode.left:
					queue.append([currNode.left, currNode])
				if currNode.right:
					queue.append([currNode.right, currNode])
		queue = deque()
		queue.append([targetNode, 0])
		currSum = 0
		visited = set()
		visited.add(targetNode.data)
		while queue:
			currQueueLen = len(queue)
			for _ in range(currQueueLen):
				(currNode, currDist) = queue.popleft()
				if currDist > k:
					return currSum
				currSum += currNode.data
				if currNode.left and currNode.left.data not in visited:
					queue.append([currNode.left, currDist + 1])
					visited.add(currNode.left.data)
				if currNode.right and currNode.right.data not in visited:
					queue.append([currNode.right, currDist + 1])
					visited.add(currNode.right.data)
				if parentLookup[currNode.data] and parentLookup[currNode.data].data not in visited:
					queue.append([parentLookup[currNode.data], currDist + 1])
					visited.add(parentLookup[currNode.data].data)
		return currSum


def distanceSum(root, d, sum, path):
	if root == None or d < 0 or (path != None and root == path):
		return
	if d >= 0:
		sum[0] += root.data
	distanceSum(root.left, d - 1, sum, path)
	distanceSum(root.right, d - 1, sum, path)

def path(root, k, p):
	if root == None:
		return False
	if root.data == k or path(root.left, k, p) or path(root.right, k, p):
		p.append(root)
		return True
	return False

class Solution:

	def sum_at_distK(self, root, target, k):
		p = []
		sum = [0]
		path(root, target, p)
		for i in range(len(p)):
			distanceSum(p[i], k - i, sum, p[i - 1] if i > 0 else None)
		return sum[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 sum_at_distK(self, root, target, k):
		q = [root]
		hm = {}
		while q:
			t = q.pop(0)
			if t.left:
				q.append(t.left)
				hm[t.left] = t
			if t.right:
				q.append(t.right)
				hm[t.right] = t
			if t.data == target:
				tn = t
		q = [tn]
		visited = {tn: 1}
		count = 0
		summ = 0
		while q and count <= k:
			arr = q[0:]
			for i in range(len(arr)):
				t = q.pop(0)
				summ += t.data
				if t.left and visited.get(t.left) == None:
					q.append(t.left)
					visited[t.left] = 1
				if t.right and visited.get(t.right) == None:
					q.append(t.right)
					visited[t.right] = 1
				if hm.get(t) and visited.get(hm[t]) == None:
					q.append(hm[t])
					visited[hm[t]] = 1
			count += 1
		return summ
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 create(self, root, parent, tar, target):
		if root == None:
			return None
		if root.data == target:
			tar[0] = root
		l = self.create(root.left, parent, tar, target)
		r = self.create(root.right, parent, tar, target)
		if l != None:
			parent[l] = root
		if r != None:
			parent[r] = root
		return root

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

	def sum_at_distK(self, root, target, k):
		(parent, visited) = ({}, {})
		parent[root] = None
		(ans, tar) = ([0], [None])
		dic = self.create(root, parent, tar, target)
		for i in parent:
			visited[i] = False
		self.check_nabor(visited, tar[0], parent, 0, ans, k)
		return ans[0]


class Solution:

	def sum_at_distK(self, root, target, k):
		parent = dict()
		start = [None]
		self.fillUpParent(root, parent, start, target)
		totalSum = 0
		visited = set()
		queue = [(start[0], 0)]
		while queue:
			(node, currentK) = queue.pop(0)
			if currentK > k:
				continue
			totalSum += node.data
			visited.add(node)
			if node in parent and parent[node] not in visited:
				queue.append((parent[node], currentK + 1))
			if node.left and node.left not in visited:
				queue.append((node.left, currentK + 1))
			if node.right and node.right not in visited:
				queue.append((node.right, currentK + 1))
		return totalSum

	def fillUpParent(self, root, parent, start, target):
		if not root:
			return
		if root.data == target and (not start[0]):
			start[0] = root
		if root.left:
			parent[root.left] = root
		if root.right:
			parent[root.right] = root
		self.fillUpParent(root.left, parent, start, target)
		self.fillUpParent(root.right, parent, start, target)


class Solution:

	def sum_at_distK(self, root, target, k):
		q = []
		q.append(root)
		parents = {}
		targetNode = Node(-1)
		while q:
			node = q.pop(0)
			if node.data == target:
				targetNode = node
			if node.left and node.left not in parents:
				parents[node.left] = node
				q.append(node.left)
			if node.right and node.right not in parents:
				parents[node.right] = node
				q.append(node.right)
		visited = {}
		visited[targetNode] = 1
		q1 = []
		q1.append(targetNode)
		lvl = 0
		Sum = 0
		while q1:
			if lvl > k:
				break
			sze = len(q1)
			for i in range(sze):
				node = q1.pop(0)
				Sum += node.data
				if node.left is not None and node.left not in visited:
					q1.append(node.left)
					visited[node.left] = 1
				if node.right is not None and node.right not in visited:
					q1.append(node.right)
					visited[node.right] = 1
				if node in parents:
					if parents[node] is not None and parents[node] not in visited:
						visited[parents[node]] = 1
						q1.append(parents[node])
			lvl += 1
		return Sum


class Solution:

	def sum_at_distK(self, root, target, k):
		parents = dict()
		queue = deque()
		queue.append(root)
		x = None
		while queue:
			curr = queue.popleft()
			if curr.data == target:
				x = curr
			if curr.left:
				parents[curr.left] = curr
				queue.append(curr.left)
			if curr.right:
				parents[curr.right] = curr
				queue.append(curr.right)
		d = dict()
		queue.clear()
		queue.append(x)
		d[x] = 1
		ans = 0
		i = 0
		while queue:
			if i > k:
				break
			i += 1
			n = len(queue)
			for j in range(n):
				root = queue.popleft()
				ans += root.data
				if root.left != None and root.left not in d:
					queue.append(root.left)
					d[root.left] = 1
				if root.right != None and root.right not in d:
					queue.append(root.right)
					d[root.right] = 1
				if root in parents and parents[root] not in d:
					queue.append(parents[root])
					d[parents[root]] = 1
		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 find_parent_and_target(self, root, parent, target):
		global d
		global node
		if not root:
			return
		if target == root.data:
			node = root
		d[root] = [parent, False]
		self.find_parent_and_target(root.left, root, target)
		self.find_parent_and_target(root.right, root, target)

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

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


class Solution:

	def sum_at_distK(self, root, target, k):
		parentmap = {}
		targetNode = self.markPar(root, parentmap, target)
		cursum = self.sumUtil(root, parentmap, targetNode)
		return cursum

	def sumUtil(self, root, parentmap, targetNode):
		cursum = 0
		que = deque()
		que.append(targetNode)
		visit = dict()
		visit[targetNode] = 1
		dis = 0
		while que:
			if dis > k:
				break
			dis += 1
			for i in range(len(que)):
				node = que.popleft()
				cursum += node.data
				if node.left and node.left not in visit:
					que.append(node.left)
					visit[node.left] = 1
				if node.right and node.right not in visit:
					que.append(node.right)
					visit[node.right] = 1
				if node in parentmap and parentmap[node] not in visit:
					que.append(parentmap[node])
					visit[parentmap[node]] = 1
		return cursum

	def markPar(self, root, parentmap, target):
		if root is None:
			return
		res = None
		q = deque()
		q.append(root)
		while q:
			node = q.popleft()
			if node.data == target:
				res = node
			if node.left:
				q.append(node.left)
				parentmap[node.left] = node
			if node.right:
				q.append(node.right)
				parentmap[node.right] = node
		return res