There is a [tree] with N nodes numbered from 1 to  N outside Harshikaa's house. The tree is rooted at node 1. Initially the tree was dry, there were no raindrops on any node of the tree. Suddenly it started raining, and every second a drop falls on all the leaf nodes of the tree. Also, every second any drop which wasn't already on the root node moves one node closer to the root.

Sometimes, strong winds shake the tree and all drops which were not on the root fall off. It is known that the wind will shake the tree M times at A_{1}, A_{2}, \ldots A_{M} seconds after it started raining. 

If multiple events happen at the same second, they are in this order:
Raindrops move one node closer to the root.
New raindrops fall on the leaves.
Wind shakes the tree.

How many drops are there at the root right after the M-th shake?

------ Input Format ------ 

- The first line of each input contains T - the number of test cases. The test cases then follow.
- The first line of each test case contains two space-separated integers N and M - the number of nodes on the tree and the number of shake events.
- N - 1 lines follow, each line containing two space-separated integers U and V denoting an edge between node U and V on the tree.
- The next line contains M space-separated integers A_{1}, A_{2}, \dots, A_{M} - the timestamp of the shakes.

------ Output Format ------ 

For each test case, output in a single line the number of raindrops on the root right after the M-th shake.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 100000$
$1 ≤ U, V ≤ N$
$U \neq V$
$1 ≤ M ≤ 100000$
$1 ≤ A_{i} ≤ 10^{9}$
$A$ is strictly increasing
- Sum of $N$ over all test cases is not more than $5 \cdot 10^{5}$
- Sum of $M$ over all test cases is not more than $4 \cdot 10^{5}$

----- Sample Input 1 ------ 
1
5 2
2 1
1 3
4 3
3 5
2 5

----- Sample Output 1 ------ 
5

----- explanation 1 ------ 
- Test case $1$: Let's define an array $R$, where $R_{i}$ is the number of raindrops on the $i$-th node.
- At second $0$, $R = [0, 0, 0, 0, 0]$.
- At second $1$, a raindrop fell on all leaves. $R$ becomes $[0, 1, 0, 1, 1]$.
- At second $2$,
- Firstly, raindrops moved closer to the root, so $R$ becomes $[1, 0, 2, 0, 0]$.
- Secondly, a raindrop fell on all leaves, so $R$ becomes $[1, 1, 2, 1, 1]$.
- Thirdly, the tree was shook, so every raindrop except the one on root fell. At the end of second $2$, $R = [1, 0, 0, 0, 0]$.

- At second $3$, new raindrops fell, and $R$ becomes $[1, 1, 0, 1, 1]$.
- At second $4$, $R$ becomes $[2, 1, 2, 1, 1]$.
- At second $5$,
- Firstly, raindrops moved closer to the root, so $R$ becomes $[5, 0, 2, 0, 0]$.
- Secondly, a raindrop fell on all leaves, so $R$ becomes $[5, 1, 2, 1, 1]$.
- Thirdly, the tree was shook, so every raindrop except the one on root fell. At the end of second $5$, $R = [5, 0, 0, 0, 0]$.

Therefore, at the end there were $5$ drops at the root.

Source: codechef | Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal


Solutions:
import sys, threading
import bisect
import math
import itertools
from sys import stdout
from heapq import heappush, heappop
import heapq
from queue import PriorityQueue
from collections import deque, defaultdict

def solve(n, tree, m, a):
	h = [0] * (n + 1)
	leafs = []
	bfs = [1]
	taken = set()
	for node in bfs:
		children_found = False
		for children in tree[node]:
			if children not in taken:
				bfs.append(children)
				h[children] = h[node] + 1
				children_found = True
		if children_found is False:
			leafs.append(node)
		taken.add(node)
	a = [0] + a
	h_leafs = []
	for leaf in leafs:
		h_leafs.append(h[leaf])
	h_leafs.sort()
	h_pre = [0]
	for i in range(len(h_leafs)):
		h_pre.append(h_pre[-1] + h_leafs[i])
	cnt = 0
	for i in range(m):
		time = a[i + 1] - a[i]
		ind = bisect.bisect_left(h_leafs, time)
		cnt += ind * time - h_pre[ind]
	return cnt
t = int(input())
ans = []
for _ in range(t):
	(n, m) = map(int, input().split())
	tree = []
	for i in range(n + 1):
		tree.append([])
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		tree[u].append(v)
		tree[v].append(u)
	a = [int(x) for x in input().split()]
	ans.append(solve(n, tree, m, a))
p = 1
for answer in ans:
	print(answer)
	p += 1


from collections import defaultdict
import bisect, sys
sys.setrecursionlimit(10 ** 5)

def dfs(i, p, dep):
	leaf = True
	for j in d[i]:
		if j == p:
			continue
		leaf = False
		dfs(j, i, dep + 1)
	if leaf:
		dist.append(dep)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = defaultdict(list)
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		d[x].append(y)
		d[y].append(x)
	A = list(map(int, input().split()))
	dist = []
	dfs(1, -1, 0)
	dist.sort()
	pre = []
	pre.append(dist[0])
	for i in range(1, len(dist)):
		pre.append(pre[i - 1] + dist[i])
	(ans, prev) = (0, 0)
	for i in range(m):
		sec = A[i] - prev
		ind = bisect.bisect_left(dist, sec)
		ind -= 1
		if ind >= 0:
			ans += sec * (ind + 1) - pre[ind]
		prev = A[i]
	print(ans)


from collections import deque
for tc in range(int(input())):
	ls = list(map(int, input().split()))
	graph = []
	for x in range(ls[0] + 1):
		graph.append([])
	for xi in range(ls[0] - 1):
		x = list(map(int, input().split()))
		graph[x[0]].append(x[1])
		graph[x[1]].append(x[0])
	que = deque()
	que.append([1, 0])
	vis = [0] * (ls[0] + 1)
	dist = [0] * (ls[0] + 1)
	leaf = []
	while len(que) > 0:
		front = que.popleft()
		(u, dis) = (front[0], front[1])
		if vis[u] == 0:
			fl = False
			for v in graph[u]:
				if vis[v] == 0:
					fl = True
					que.append([v, dis + 1])
					dist[v] = dist[u] + 1
			if fl == False:
				leaf.append(u)
			vis[u] = 1
	dic = dict()
	new = []
	for x in leaf:
		if dic.get(dist[x]) is None:
			dic[dist[x]] = 1
			new.append(dist[x])
		else:
			dic[dist[x]] += 1
	new.sort()
	pre1 = []
	pre2 = []
	for x in new:
		if len(pre2) == 0:
			pre1.append(x * dic[x])
			pre2.append(dic[x])
		else:
			pre1.append(pre1[-1] + dic[x] * x)
			pre2.append(pre2[-1] + dic[x])
	op = list(map(int, input().split()))
	pre = [1]
	ans = 0
	for x in range(len(op)):
		time = op[x] - pre[-1] + 1
		pre.append(op[x] + 1)
		lo = 0
		hi = len(new) - 1
		tar = -1
		while lo <= hi:
			mid = (lo + hi) // 2
			if new[mid] < time:
				tar = mid
				lo = mid + 1
			else:
				hi = mid - 1
		if tar != -1:
			ans += time * pre2[tar] - pre1[tar]
	print(ans)


import threading
import sys
from sys import stdin
input = stdin.readline
sys.setrecursionlimit(10 ** 8)
from collections import defaultdict

def main():
	from bisect import bisect, bisect_left, bisect_right
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		child = [[] * (n + 1) for _ in range(n + 1)]
		for i in range(n - 1):
			(u, v) = map(int, input().split())
			child[u].append(v)
			child[v].append(u)
		a = list(map(int, input().split()))
		dist = []

		def dfs(p, prev, level):
			yes = True
			for i in child[p]:
				if i == prev:
					continue
				yes = False
				dfs(i, p, level + 1)
			if yes:
				dist.append(level)
		dfs(1, -1, 1)
		dist.sort()
		prefix = [0]
		for el in dist:
			prefix.append(el + prefix[-1])
		prev = 0
		ans = 0
		for i in range(m):
			gap = a[i] - prev
			ind = bisect_right(dist, gap)
			ans += ind
			ans += gap * ind - prefix[ind]
			prev = a[i]
		print(ans)
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


from sys import stdin
input = stdin.readline
from queue import Queue
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	adj = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u - 1].append(v - 1)
		adj[v - 1].append(u - 1)
	a = [0]
	a.extend(list(map(int, input().split())))
	q = Queue()
	q.put([0, 0, -1])
	ind = -1
	paths = []
	while not q.empty():
		li = q.get()
		node = li[0]
		ind = li[1]
		if len(adj[node]) == 1 and node != 0:
			paths.append(ind)
		else:
			for i in range(len(adj[node])):
				if adj[node][i] != li[2]:
					q.put([adj[node][i], ind + 1, node])
	for i in range(len(paths)):
		paths[i] += 1
	d = {}
	for i in range(len(paths)):
		if paths[i] not in d:
			d[paths[i]] = 0
		d[paths[i]] += 1
	keys = list(d.keys())
	mx = max(keys)
	aa = [0] * (mx + 1)
	vv = sum(d.values())
	active = 0
	curr = 0
	for i in range(len(aa)):
		if d.get(i):
			active += d[i]
			curr += active
			aa[i] = curr
		else:
			curr += active
			aa[i] = curr
	dd = {}
	for i in range(1, m + 1):
		time = a[i] - a[i - 1]
		if time not in dd:
			dd[time] = 0
		dd[time] += 1
	ans = 0
	for (k, v) in dd.items():
		if k > mx:
			ans = ans + (aa[mx] + (k - mx) * active) * v
		else:
			ans = ans + aa[k] * v
	print(ans)


def next(arr, target):
	start = 0
	end = len(arr) - 1
	ans = len(arr)
	while start <= end:
		mid = (start + end) // 2
		if arr[mid] <= target:
			start = mid + 1
		else:
			ans = mid
			end = mid - 1
	return ans
from collections import deque
t = int(input())
for z in range(t):
	(n, m) = map(int, input().split())
	adj = dict()
	for i in range(1, n + 1):
		adj[i] = set()
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		adj[a].add(b)
		adj[b].add(a)
	a = list(map(int, input().split()))
	q = deque([[1, 0]])
	visited = [0] * (n + 1)
	visited[1] = 1
	leaf = dict()
	while q:
		node = q.popleft()
		if len(adj[node[0]]) == 1 and node[0] != 1:
			if node[1] in leaf:
				leaf[node[1]] += 1
			else:
				leaf[node[1]] = 1
			continue
		for n in adj[node[0]]:
			if visited[n] == 0:
				q.append([n, node[1] + 1])
				visited[n] = 1
	diff = [a[0]]
	for i in range(1, m):
		diff.append(a[i] - a[i - 1])
	diff.sort()
	s = [0, diff[0]]
	for i in range(1, m):
		s.append(s[-1] + diff[i])
	ans = 0
	for level in leaf:
		count = 0
		index = next(diff, level)
		if index != m:
			count += s[m] - s[index] - level * (m - index)
		ans += count * leaf[level]
	print(ans)


from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(10 ** 7)

def dfs(p, prev, level):
	yes = True
	for i in child[p]:
		if i == prev:
			continue
		yes = False
		dfs(i, p, level + 1)
	if yes:
		dist.append(level)

def b_s(key):
	(l, h) = (0, len(dist) - 1)
	ans = -1
	while l <= h:
		mid = (l + h) // 2
		if dist[mid] <= key:
			ans = mid
			l = mid + 1
		else:
			h = mid - 1
	return ans

def answer():
	ans = 0
	prev = 0
	for i in range(m):
		d = a[i] - prev
		ind = b_s(d)
		if ind != -1:
			ans += (ind + 1) * d - prefix[ind] + (ind + 1)
		prev = a[i]
	return ans
for T in range(int(input())):
	(n, m) = map(int, input().split())
	child = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		child[u].append(v)
		child[v].append(u)
	a = list(map(int, input().split()))
	dist = []
	dfs(1, -1, 1)
	dist.sort()
	prefix = [dist[0]]
	for i in range(1, len(dist)):
		prefix.append(prefix[-1] + dist[i])
	print(answer())


from collections import defaultdict
import bisect
import sys
sys.setrecursionlimit(10 ** 7)
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	adj = defaultdict(list)
	leaf = defaultdict(int)
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		adj[u].append(v)
		adj[v].append(u)

	def dfs(u, p, depth):
		count = 0
		for v in adj[u]:
			if v == p:
				continue
			count += 1
			dfs(v, u, depth + 1)
		if count == 0:
			leaf[depth] += 1
	dfs(0, 0, 1)
	A = [int(x) for x in input().split()]
	gap = [0] * m
	gap[0] = A[0]
	for i in range(1, m):
		gap[i] = A[i] - A[i - 1]
	gap.sort()
	pref = [0] * m
	pref[m - 1] = gap[m - 1]
	for i in range(m - 2, -1, -1):
		pref[i] = pref[i + 1] + gap[i]
	drops = 0
	for (key, val) in leaf.items():
		count = 0
		depth = key
		lb = bisect.bisect_left(gap, depth)
		if lb >= m:
			continue
		num = m - lb
		depth -= 1
		ans = pref[lb] - num * depth
		drops += ans * val
	print(drops)


def main():
	alpha = 'abcdefghijklmnopqrstuvwxyz'
	ALPHA = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
	inf = 1e+17
	mod = 10 ** 9 + 7
	Max = 2 * 10 ** 6
	primes = []
	prime = [True for i in range(Max + 1)]
	p = 2
	while p * p <= Max + 1:
		if prime[p] == True:
			for i in range(p * p, Max + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, Max + 1):
		if prime[p]:
			primes.append(p)
	primes = set(primes)

	def factorial(n):
		f = 1
		for i in range(1, n + 1):
			f = f * i % mod
		return f

	def factorial_by(n, by):
		f = 1
		for i in range(1, n + 1):
			if i == by:
				continue
			f = f * i % mod
		return f

	def ncr(n, r):
		num = den = 1
		for i in range(r):
			num = num * (n - i) % mod
			den = den * (i + 1) % mod
		return num * pow(den, mod - 2, mod) % mod

	def primeFactors(num):
		pf = []
		while num % 2 == 0:
			pf.append(2)
			num = num // 2
		for i in range(3, int(math.sqrt(num)) + 1, 2):
			while num % i == 0:
				pf.append(i)
				num = num // i
		if num > 2:
			pf.append(num)
		return pf

	class Node(object):

		def __init__(self, anc, s):
			self.anc = anc
			self.s = s

		def __repr__(self):
			return str(self.s)
			pass

	class DSU:

		def __init__(self, n):
			self.parent = list(range(n))
			self.size = [1] * n
			self.num_sets = n

		def find(self, a):
			acopy = a
			while a != self.parent[a]:
				a = self.parent[a]
			while acopy != a:
				(self.parent[acopy], acopy) = (a, self.parent[acopy])
			return a

		def union(self, a, b):
			(a, b) = (self.find(a), self.find(b))
			if a != b:
				if self.size[a] < self.size[b]:
					(a, b) = (b, a)
				self.num_sets -= 1
				self.parent[b] = a
				self.size[a] += self.size[b]

	def floor(a, b):
		val = a // b
		while val * b > a:
			val -= 1
		return val

	def solve(n, tree, m, a):
		h = [0] * (n + 1)
		leafs = []
		bfs = [1]
		taken = set()
		for node in bfs:
			children_found = False
			for children in tree[node]:
				if children not in taken:
					bfs.append(children)
					h[children] = h[node] + 1
					children_found = True
			if children_found is False:
				leafs.append(node)
			taken.add(node)
		a = [0] + a
		h_leafs = []
		for leaf in leafs:
			h_leafs.append(h[leaf])
		h_leafs.sort()
		h_pre = [0]
		for i in range(len(h_leafs)):
			h_pre.append(h_pre[-1] + h_leafs[i])
		cnt = 0
		for i in range(m):
			time = a[i + 1] - a[i]
			ind = bisect.bisect_left(h_leafs, time)
			cnt += ind * time - h_pre[ind]
		return cnt
	t = int(input())
	ans = []
	for _ in range(t):
		(n, m) = map(int, input().split())
		tree = []
		for i in range(n + 1):
			tree.append([])
		for i in range(n - 1):
			(u, v) = map(int, input().split())
			tree[u].append(v)
			tree[v].append(u)
		a = [int(x) for x in input().split()]
		ans.append(solve(n, tree, m, a))
	p = 1
	for answer in ans:
		print(answer)
		p += 1
import sys, threading
import bisect
import math
import itertools
from sys import stdout
from heapq import heappush, heappop
import heapq
from queue import PriorityQueue
from collections import deque, defaultdict
input = sys.stdin.readline
thread = threading.Thread(target=main)
thread.start()
thread.join()