You are given a tree rooted at node $1$ with $N$ vertices. The $i$$th$ vertex initially has value $A_i (1 \leq i \leq N)$. You are also given $Q$ queries. 
In each query you are given a vertex $V$.  Let $S = \{ S_1 , S_2 , ... S_x \} $ denote the set of vertices such that $S_i$ is in the subtree of $V$, distance between $S_i$ and $V$ is even and $S_i \neq V$ for all $i$. For all $S_i$ , add $A$$S_i$ to $A_V$ and change the value of $A$$S_i$ to zero.
Find the values of all the vertices after all queries are performed. 
Note-The distance between two vertices is defined as the number of edges
traversed on the shortest path from one vertex to the other.

-----Input:-----
- The first line contains an integer $T$ denoting the number of test cases.
- The first line of each test case contain two integers $N$ and $Q$.
- The second line contains $N$ space separated integers, $A_1, A_2, ..., A_n$ denoting the initial values of the vertices.
- The next $N-1$ lines contain two integers $u$ and $v$ denoting an edge between $u$and $v$.
- The next $Q$ lines contain a single integer which is the query.

-----Output:-----
- Print a single line containing $N$ integers for each test case which is the final values of the vertices.

-----Constraints:-----
- $1\leq T \leq 10$
- $1 \leq N \leq 200000$
- $1 \leq Q \leq 200000$
- $0 \leq A_i \leq 10^9$
- The sum of $N$ over all test cases does not exceed $200000$.
- The sum of $Q$ over all test cases does not exceed $200000$.

-----Sample Input-----
1
4 3
6 2 7 3
1 2
2 3
3 4
3
2
1

-----Sample Output-----
13 5 0 0

-----Explanation-----
Node $3$ has no child in its subtree which is at  an even distance so there is no change in the values. Values of nodes after $1st$ query: $6, 2, 7, 3$.
Node $4$ is at an even distance in the subtree of node $2$ so $A_4$ gets added to $A_2$ and $A_4$ becomes 0. Values of nodes after $2nd$ query: $6, 5, 7, 0$.
Node $3$ is at an even distance in the subtree of node $1$ so $A_3$ gets added to $A_1$ and $A_3$ becomes 0. Values of nodes after $3rd$ query: $13, 5, 0, 0$.

Source: codechef | Difficulty: VERY_HARD
Tags: Tree algorithms

Graph algorithms

Data structures

Graph traversal


Solutions:
from collections import defaultdict as dd, deque as dq

def opbfs(u, vis, ll, parr):
	q = dq([(u, 0)])
	uu = u
	su = 0
	while q:
		(u, lol) = q.pop()
		par = parr[u]
		if lol % 2 == 0:
			vis[u] = 1
			su += ll[u - 1]
			ll[u - 1] = 0
		for j in d[u]:
			if j != par:
				q.appendleft((j, lol + 1))
	ll[uu - 1] = su

def bfs(height, d, parr):
	q = dq([1])
	while q:
		u = q.pop()
		height[u] = height[parr[u]] + 1
		for i in d[u]:
			if i != parr[u]:
				q.appendleft(i)
				parr[i] = u
t = int(input())
while t:
	(n, q) = map(int, input().split())
	ll = list(map(int, input().split()))
	d = dd(list)
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		d[u].append(v)
		d[v].append(u)
	vis = [0] * (n + 1)
	l = []
	height = [0] * (n + 1)
	parr = [0] * (n + 1)
	bfs(height, d, parr)
	for i in range(q):
		u = int(input())
		l.append((height[u], u, i))
	l.sort()
	vis = [0] * (n + 1)
	for i in l:
		(he, u, ind) = i
		if vis[u] == 0:
			opbfs(u, vis, ll, parr)
	print(*ll)
	t -= 1


import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 998244353
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	values = list(map(int, input().split()))
	tree = [set() for i in range(n)]
	grandchildren = [list() for i in range(n)]
	for ni in range(n - 1):
		(u, v) = map(int, input().split())
		tree[u - 1].add(v - 1)
		tree[v - 1].add(u - 1)
	queue = deque([(0, -1)])
	while queue:
		(parent, grandparent) = queue.pop()
		for children in tree[parent]:
			tree[children].remove(parent)
			if grandparent != -1:
				grandchildren[grandparent].append(children)
			queue.append((children, parent))
	for qi in range(q):
		query = int(input()) - 1
		if not grandchildren[query]:
			continue
		queue = deque([query])
		while queue:
			node = queue.pop()
			for g in grandchildren[node]:
				values[query] += values[g]
				values[g] = 0
				queue.append(g)
			grandchildren[node] = []
	print(' '.join(map(str, values)))