Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given a tree with $N$ nodes (numbered $1$ through $N$). For each valid $i$, node $i$ has a value $A_{i}$.

You should answer $Q$ queries. In each query:
You are given two nodes $a$ and $b$.
Let $S$ denote the set of all nodes on the simple path between the nodes $a$ and $b$ (including these nodes).
Find the minimum value of $|A_{x}-A_{y}|$ over all pairs $x, y \in S$ such that $x \neq y$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $Q$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.
Each of the next $N-1$ lines contains two space-separated integers $u$ and $v$ denoting that nodes $u$ and $v$ are connected by an edge.
Each of the last $Q$ lines contains two space-separated integers $a$ and $b$ describing a query.

------  Output ------
For each query, print a single line containing one integer ― the answer to the query.

------  Constraints ------
$1 ≤ T ≤ 20$
$2 ≤ N ≤ 2 \cdot 10^{5}$
$1 ≤ Q ≤ 2 \cdot 10^{5}$
$1 ≤ A_{i} ≤ 100$ for each valid $i$
$1 ≤ u, v, a, b ≤ N$
$a \neq b$
the sum of $N$ over all test cases does not exceed $5 \cdot 10^{5}$
the sum of $Q$ over all test cases does not exceed $5 \cdot 10^{5}$

------  Subtasks ------
Subtask #1 (30 points): $N, Q ≤ 1,000$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
1

6 3

10 2 5 6 5 6

1 2

2 3

2 4

1 5

5 6

5 6

3 5

1 4
----- Sample Output 1 ------ 
1

0

4
----- explanation 1 ------ 
Example case 1:
- For the first query, $S=\{5, 6\}$, so the answer is $|A_{5}-A_{6}|=1$.
- For the second query, $S=\{3, 2, 1, 5\}$ and we can see that $|A_{3}-A_{5}|=0$.
- For the third query, $S=\{1, 2, 4\}$.

Source: codechef | Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal

Tree algorithms

Mathematics

Data structures

Tree queries


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

def main():
	for _ in range(int(input())):
		(nodes, queries) = map(int, input().split())
		cost = list(map(int, input().split()))
		graph = [[] for _ in range(nodes)]

		def dfs(node, par):
			if node == 0:
				parent[0] = -1
				height[0] = 0
			else:
				parent[node] = par
				height[node] = height[par] + 1
			for child in graph[node]:
				if child == par:
					continue
				else:
					dfs(child, node)
		for _ in range(nodes - 1):
			(a, b) = map(int, input().split())
			a -= 1
			b -= 1
			graph[a].append(b)
			graph[b].append(a)
		parent = [0] * nodes
		height = [0] * nodes
		dfs(0, -1)
		for _ in range(queries):
			(a, b) = map(int, input().split())
			a -= 1
			b -= 1
			if height[a] < height[b]:
				(a, b) = (b, a)
			ans = []
			while height[a] != height[b] and len(ans) <= 100:
				ans.append(cost[a])
				a = parent[a]
			while a != b and len(ans) <= 100:
				ans.append(cost[a])
				ans.append(cost[b])
				a = parent[a]
				b = parent[b]
			ans.append(cost[b])
			if len(ans) > 100:
				print(0)
			else:
				ans.sort()
				res = float('inf')
				for i in range(len(ans) - 1):
					res = min(res, ans[i + 1] - ans[i])
				print(res)
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


import sys

def fop(s, end='\n'):
	sys.stdout.write(str(s) + end)

def fip():
	return sys.stdin.readline().strip()

def solve():
	elements = set()
	(u, v) = map(int, fip().split())
	flag = True
	if depth[u] < depth[v]:
		(u, v) = (v, u)
	while depth[u] > depth[v]:
		if a[u - 1] not in elements:
			elements.add(a[u - 1])
		else:
			return 0
		u = parent[u]
	while u != v:
		if a[u - 1] not in elements:
			elements.add(a[u - 1])
		else:
			return 0
		if a[v - 1] not in elements:
			elements.add(a[v - 1])
		else:
			return 0
		u = parent[u]
		v = parent[v]
	if a[u - 1] not in elements:
		elements.add(a[u - 1])
	else:
		return 0
	ans = 100
	elements = sorted(elements)
	for i in range(1, len(elements)):
		ans = min(ans, abs(elements[i] - elements[i - 1]))
		if ans == 1:
			return 1
	return ans
from collections import deque
t = int(fip())
while t > 0:
	t -= 1
	(n, queries) = map(int, fip().split())
	tree = [set() for i in range(n + 1)]
	a = [int(x) for x in fip().split()]
	for i in range(n - 1):
		(u, v) = map(int, fip().split())
		tree[u].add(v)
		tree[v].add(u)
	depth = [-1 for i in range(n + 1)]
	parent = [-1 for i in range(n + 1)]
	parent[1] = 0
	depth[1] = 0
	q = deque([1])
	while len(q) != 0:
		curr = q.popleft()
		for child in tree[curr]:
			if depth[child] < 0:
				q.append(child)
				depth[child] = depth[curr] + 1
				parent[child] = curr
	for i in range(queries):
		fop(solve())


from collections import deque

def readTree(n):
	adj = [set() for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u - 1].add(v - 1)
		adj[v - 1].add(u - 1)
	return adj

def main():

	def solve():
		(n, q) = map(int, input().split())
		aa = [int(a) for a in input().split()]
		adj = readTree(n)
		dq = deque()
		dq.append(0)
		parent = [-2] + [-1] * (n - 1)
		depth = [0] * n
		parent[0] = 0
		while dq:
			nd = dq.popleft()
			for a in adj[nd]:
				if parent[a] < 0:
					parent[a] = nd
					depth[a] = depth[nd] + 1
					dq.append(a)

		def solve1():
			(a, b) = map(int, input().split())
			a -= 1
			b -= 1
			values = set()
			if depth[b] > depth[a]:
				(b, a) = (a, b)
			while depth[a] > depth[b]:
				if aa[a] in values:
					print(0)
					return
				values.add(aa[a])
				a = parent[a]
			while a != b:
				if aa[a] in values:
					print(0)
					return
				values.add(aa[a])
				a = parent[a]
				if aa[b] in values:
					print(0)
					return
				values.add(aa[b])
				b = parent[b]
			if aa[a] in values:
				print(0)
				return
			values.add(aa[a])
			lv = list(values)
			lv.sort()
			mn = n
			for i in range(len(lv) - 1):
				mn = min(lv[i + 1] - lv[i], mn)
				if mn == 1:
					break
			print(mn)
		for _ in range(q):
			solve1()
	t = int(input())
	for _ in range(t):
		solve()
main()


from collections import defaultdict
from collections import deque
import sys

def fop(s, end='\n'):
	sys.stdout.write(str(s) + end)

def fip():
	return sys.stdin.readline().strip()

def find_parent_and_depth(curr: int, prev: int=-1, depth1: int=0) -> None:
	d = deque()
	parent[curr] = prev
	depth[curr] = 0
	d.append(curr)
	while d:
		node = d.popleft()
		for n in tree[node]:
			if parent[n] == -2:
				parent[n] = node
				depth[n] = depth[node] + 1
				d.append(n)

def solve(a: int, b: int) -> int:
	arr = set()
	while a != b:
		if depth[a] > depth[b]:
			if a_list[a] in arr:
				return 0
			arr.add(a_list[a])
			a = parent[a]
		else:
			if a_list[b] in arr:
				return 0
			arr.add(a_list[b])
			b = parent[b]
	if a_list[a] in arr:
		return 0
	arr.add(a_list[a])
	l = sorted(arr)
	res = float('inf')
	for (p, n) in zip(l, l[1:]):
		res = min(res, abs(p - n))
	return res
N = 200005
t = int(fip())
for _ in range(t):
	tree = [0] * N
	parent = [-2] * N
	depth = [-2] * N
	(n, q) = map(int, fip().split())
	a_list = list(map(int, fip().split()))
	for _ in range(n - 1):
		(u, v) = map(int, fip().split())
		if tree[u - 1] == 0:
			tree[u - 1] = set()
		if tree[v - 1] == 0:
			tree[v - 1] = set()
		tree[u - 1].add(v - 1)
		tree[v - 1].add(u - 1)
	t = find_parent_and_depth(0)
	for _ in range(q):
		(a, b) = map(int, fip().split())
		res = solve(a - 1, b - 1)
		fop(res)


from collections import deque

def solve(parent, depth, aa):
	(a, b) = list(map(int, input().split()))
	a -= 1
	b -= 1
	values = set()
	if depth[b] > depth[a]:
		(a, b) = (b, a)
	while depth[a] > depth[b]:
		if aa[a] in values:
			return 0
		values.add(aa[a])
		a = parent[a]
	while a != b:
		if aa[a] in values:
			return 0
		values.add(aa[a])
		a = parent[a]
		if aa[b] in values:
			return 0
		values.add(aa[b])
		b = parent[b]
	if aa[a] in values:
		return 0
	values.add(aa[a])
	l = list(values)
	l.sort()
	mn = 1000000.0
	for i in range(len(l) - 1):
		mn = min(mn, l[i + 1] - l[i])
		if mn == 1:
			break
	return mn
for T in range(int(input())):
	(n, q) = list(map(int, input().split()))
	aa = list(map(int, input().split()))
	adj = [set() for i in range(n)]
	for i in range(n - 1):
		(u, v) = list(map(int, input().split()))
		adj[u - 1].add(v - 1)
		adj[v - 1].add(u - 1)
	parent = [-1] * n
	parent[0] = 0
	depth = [0] * n
	dq = deque()
	dq.append(0)
	while dq:
		p = dq.popleft()
		for i in adj[p]:
			if parent[i] < 0:
				parent[i] = p
				depth[i] = depth[p] + 1
				dq.append(i)
	for i in range(q):
		v = solve(parent, depth, aa)
		print(v)


def bfs(length):
	queue = [1] * (length + 1)
	pos = 1
	level[1] = 0
	while pos >= 1:
		pushed_node = queue[pos]
		pos -= 1
		depth = level[pushed_node] + 1
		for node in tree[pushed_node]:
			if level[node] == -1:
				level[node] = depth
				parent[node] = pushed_node
				pos += 1
				queue[pos] = node

def addEdge(first, second):
	tree[first].append(second)
	tree[second].append(first)

def treeDiff(node_a, node_b):
	frequency = [0] * 101
	while node_a != node_b:
		if level[node_a] > level[node_b]:
			if frequency[value[node_a]] == 1:
				return 0
			frequency[value[node_a]] += 1
			node_a = parent[node_a]
		else:
			if frequency[value[node_b]] == 1:
				return 0
			frequency[value[node_b]] += 1
			node_b = parent[node_b]
	if frequency[value[node_a]] == 1:
		return 0
	frequency[value[node_a]] += 1
	diff = 101
	previous = -101
	for i in range(1, 101):
		if frequency[i] == 1:
			diff = min(diff, i - previous)
			previous = i
	return diff
t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	value = list(map(int, input().split()))
	value.insert(0, -1)
	tree = []
	for i in range(n + 1):
		tree.append([])
	parent = [0] * (n + 1)
	level = [-1] * (n + 1)
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		addEdge(u, v)
	bfs(n)
	for i in range(q):
		(u, v) = map(int, input().split())
		print(treeDiff(u, v))


import sys

def fop(s, end='\n'):
	sys.stdout.write(str(s) + end)

def fip():
	return sys.stdin.readline().strip()
fintinp = lambda : int(fip())

def flistinp(func=int):
	return list(map(func, fip().split()))

def fnsepline(n, func=str):
	return [func(fip()) for _ in range(n)]
from collections import deque, defaultdict

class Graph:

	def __init__(self, n=None):
		self.node_count = n
		self.adj_list = defaultdict(list)

	def add_edge(self, u, v, w=0):
		if 1:
			self.adj_list[u].append([v, w])
			self.adj_list[v].append([u, w])

	def bfs(self, start=1):

		def _bfs(start, graph=self.adj_list):
			level = defaultdict(lambda : None)
			level[start] = 0
			q = deque([])
			q.append(start)
			visited = defaultdict(lambda : False)
			visited[start] = True
			prev = defaultdict(lambda : None)
			while q:
				node = q.popleft()
				neighbours = graph[node]
				for (next_v, w) in neighbours:
					if not visited[next_v]:
						level[next_v] = level[node] + 1
						q.append(next_v)
						visited[next_v] = True
						prev[next_v] = node
			return (prev, level)
		return _bfs(start)

def make_path(start, end, wt, prev, levels):
	if levels[start] < levels[end]:
		(start, end) = (end, start)
	weights = set([])
	while levels[start] != levels[end]:
		if wt[start - 1] in weights:
			fop(0)
			return
		weights.add(wt[start - 1])
		start = prev[start]
	while start != end:
		if wt[start - 1] in weights:
			fop(0)
			return 0
		weights.add(wt[start - 1])
		if wt[end - 1] in weights:
			print(0)
			return 0
		weights.add(wt[end - 1])
		start = prev[start]
		end = prev[end]
	if wt[end - 1] in weights:
		fop(0)
		return
	weights.add(wt[end - 1])
	weights = list(weights)
	weights.sort()
	fop(min([abs(weights[i] - weights[i + 1]) for i in range(len(weights) - 1)]))
	return
for _ in range(fintinp()):
	(n, q) = map(int, fip().split())
	wt = flistinp()
	g = Graph(n=n)
	for _ in range(n - 1):
		(u, v) = map(int, fip().split())
		g.add_edge(u, v, 0)
	(prev, levels) = g.bfs()
	for q_ in range(q):
		(a, b) = map(int, fip().split())
		make_path(a, b, wt, prev, levels)


from collections import deque
from sys import stdin

def II():
	return int(stdin.readline())

def MI():
	return map(int, stdin.readline().split())

def LI():
	return list(map(int, stdin.readline().split()))

class tree:

	def __init__(self, V):
		self.nodes = V
		self.adj = [[] for i in range(V)]
		self.parent = [-1] * V
		self.level = [-1] * V

def addEdge(ta, v, w):
	ta.adj[v].append(w)
	ta.adj[w].append(v)

def BFS(ta, s):
	queue = deque([s])
	ta.level[s] = 0
	while queue:
		x = queue.popleft()
		for i in ta.adj[x]:
			if ta.level[i] == -1:
				ta.level[i] = ta.level[x] + 1
				ta.parent[i] = x
				queue.append(i)

def readUV():
	(u, v) = MI()
	(u, v) = (u - 1, v - 1)
	return (u, v)

def solve(ta, a, b, aa):
	if ta.level[a] < ta.level[b]:
		(a, b) = (b, a)
	vals = set()
	while ta.level[b] != ta.level[a]:
		if aa[a] in vals:
			print(0)
			return
		vals.add(aa[a])
		a = ta.parent[a]
	while b != a:
		if aa[a] in vals:
			print(0)
			return
		vals.add(aa[a])
		if aa[b] in vals:
			print(0)
			return
		vals.add(aa[b])
		(a, b) = (ta.parent[a], ta.parent[b])
	if aa[a] in vals:
		print(0)
		return
	vals.add(aa[a])
	(ans, x) = (101, len(vals))
	vals = list(vals)
	vals.sort()
	for j in range(1, x):
		ans = min(ans, vals[j] - vals[j - 1])
		if ans == 1:
			break
	print(ans)
t = II()
for _ in range(t):
	(n, q) = MI()
	aa = LI()
	atree = tree(n)
	for i in range(n - 1):
		(u, v) = readUV()
		addEdge(atree, u, v)
	BFS(atree, 0)
	for i in range(q):
		(a, b) = readUV()
		solve(atree, a, b, aa)


import sys
sys.setrecursionlimit(1000000)
from sys import stdin, stdout
maxn = 180000
level = 18
from collections import defaultdict
from collections import deque

def minans(l):
	l.sort()
	ans = float('inf')
	for i in range(len(l) - 1):
		ans = min(ans, l[i + 1] - l[i])
	return ans

def dfs(cur, prev):
	depth[cur] = depth[prev] + 1
	parent[cur][0] = prev
	for i in range(len(tree[cur])):
		if tree[cur][i] != prev:
			dfs(tree[cur][i], cur)

def precomputeSparseMatrix(n):
	for i in range(1, level):
		for node in range(1, n + 1):
			if parent[node][i - 1] != -1:
				parent[node][i] = parent[parent[node][i - 1]][i - 1]

def LCA(u, v):
	if depth[v] < depth[u]:
		(u, v) = (v, u)
	diff = depth[v] - depth[u]
	for i in range(level):
		if diff >> i & 1:
			v = parent[v][i]
	if u == v:
		return u
	for i in range(level - 1, -1, -1):
		if parent[u][i] != parent[v][i]:
			u = parent[u][i]
			v = parent[v][i]
	return parent[u][0]

def addEdge(u, v):
	tree[u].append(v)
	tree[v].append(u)

def Bfs(src):
	visited = defaultdict(bool)
	dist = defaultdict(int)
	q = deque([])
	q.append(src)
	visited[src] = True
	dist[src] = 1
	while q:
		node = q.popleft()
		for neighbour in tree[node]:
			if not visited[neighbour]:
				q.append(neighbour)
				visited[neighbour] = True
				dist[neighbour] = dist[node] + 1
				parent2[neighbour] = node
	return dist
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	maxn = n + 1
	arr = list(map(int, stdin.readline().split()))
	tree = [[] for i in range(n + 1)]
	parent2 = [-1] * (n + 1)
	for i in range(n - 1):
		(x, y) = map(int, stdin.readline().split())
		if i == 0:
			root = x
		addEdge(x, y)
	parent = [[-1] * level for j in range(maxn)]
	depth = [None] * maxn
	depth[0] = 0
	dfs(root, 0)
	precomputeSparseMatrix(n)
	dist = Bfs(root)
	for i in range(q):
		(x, y) = map(int, stdin.readline().split())
		if x == y:
			ans = 0
		else:
			lca = LCA(x, y)
			if x == lca and y != lca:
				ch = dist[y] - dist[lca] + 1
				if ch <= 100:
					path = []
					temp = y
					while temp != lca:
						path.append(arr[temp - 1])
						temp = parent2[temp]
					path.append(arr[lca - 1])
					ans = minans(path)
				else:
					ans = 0
			elif x != lca and y == lca:
				ch = dist[x] - dist[lca] + 1
				if ch <= 100:
					path = []
					temp = x
					while temp != lca:
						path.append(arr[temp - 1])
						temp = parent2[temp]
					path.append(arr[lca - 1])
					ans = minans(path)
				else:
					ans = 0
			else:
				ch = dist[x] - dist[lca] + (dist[y] - dist[lca]) + 1
				if ch <= 100:
					path = []
					temp = x
					while temp != lca:
						path.append(arr[temp - 1])
						temp = parent2[temp]
					temp = y
					while temp != lca:
						path.append(arr[temp - 1])
						temp = parent2[temp]
					path.append(arr[lca - 1])
					ans = minans(path)
				else:
					ans = 0
		stdout.write(str(ans))
		print()


from sys import stdin, stdout

def find(A, B, dep, par, arr):
	(A, B) = sorted([A, B], key=lambda x: dep[x])
	freq = [0] * 101
	c = 0
	while dep[A] != dep[B]:
		freq[arr[B]] += 1
		if freq[arr[B]] > 1:
			return 0
		B = par[B]
		c += 1
		if c > 100:
			return 0
	while A != B:
		freq[arr[A]] += 1
		freq[arr[B]] += 1
		if freq[arr[B]] > 1 or freq[arr[A]] > 1:
			return 0
		(A, B) = (par[A], par[B])
		c += 2
		if c > 100:
			return 0
	freq[arr[A]] += 1
	if freq[arr[A]] > 1:
		return 0
	k = freq.index(1)
	m = float('inf')
	for i in range(k + 1, 101):
		if freq[i]:
			m = min(m, i - k)
			k = i
	return m

def main():
	for _ in range(int(stdin.readline())):
		(N, M) = list(map(int, stdin.readline().split()))
		arr = list(map(int, stdin.readline().split()))
		graph = [[] for _ in range(N)]
		for __ in range(N - 1):
			(A, B) = list(map(int, stdin.readline().split()))
			graph[A - 1].append(B - 1)
			graph[B - 1].append(A - 1)
		(dep, par) = ([-1] * N, [-1] * N)
		que = [0]
		(par[0], dep[0]) = (0, 0)
		for root in que:
			for k in graph[root]:
				if k == par[root]:
					continue
				par[k] = root
				dep[k] = dep[root] + 1
				que.append(k)
		for __ in range(M):
			(A, B) = list(map(int, stdin.readline().split()))
			print(find(A - 1, B - 1, dep, par, arr))
main()