Chef is given a rooted tree with N nodes numbered 1 to N where 1 is the root node.  
Each node is assigned a lowercase english alphabet between a to z (both included). 

Given two nodes A and B:
Let LCA(A, B) denote the [lowest common ancestor] of nodes A and B.
Let DIS(A,B) denote the string containing all the characters associated with the nodes in the same order as the shortest path from node A to node B (excluding the character associated to node B). Note that DIS(A,A) is an empty string.

Chef needs to answer Q queries. Each query is of the type:
U V: Given two integers U and V (1≤ U,V ≤ N), determine if there exists a concatenation of a non-empty [subsequence] and a non-empty subsequence of DIS(V,LCA(U,V)) such that it is a [palindrome].

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

- The first line of each test case contains T, the number of test cases.
- The second line of each test case contains N, the number of nodes in the tree.
- The third line of each test case contains a string S consisting of N characters. Here, S_{i} corresponds to the character associated with node i.
- The next (N-1) lines each contain two space-separated integers x and y, denoting that an edge exists between nodes x and y.
- The next line contains Q, the number of queries.
- The next Q lines each contain two space-separated integers U and V, denoting the query.

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

For each test case, output Q lines. Print YES in the i^{th} line if there exist a concatenation of a non-empty [subsequence] and a non-empty subsequence of DIS(V,LCA(U,V)) such that it is a palindrome for the i^{th} query. Otherwise, print NO.

You may print each character of the string in uppercase or lowercase (for example, the strings YES, yEs, yes, and yeS will all be treated as identical).

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

$1 ≤T ≤2 \cdot 10^{5}$
$2 ≤N ≤2 \cdot 10^{5}$
$1 ≤Q ≤2 \cdot 10^{5}$
$1≤x, y ≤N$ and $x\ne y$.
$1 ≤U,V ≤N$ and $U \ne V$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.
- Sum of $Q$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
1
7
ydbxcbd
1 2
2 3
1 4
2 5
6 4
7 6
2
3 5
3 6
----- Sample Output 1 ------ 
NO
YES
----- explanation 1 ------ 
The tree looks like:

Query $1$: $LCA(3, 5) = 2$. $DIS(3, LCA(3,5)) = DIS(3,2) = $ b. Similarly, $DIS(5, LCA(3,5)) = DIS(5,2) = $ c. It is not possible to concatenate non-empty subsequences from $DIS(3,2)$ and $DIS(5,2)$ such that we get a palindrome.

Query $2$: $LCA(3, 6) = 1$. $DIS(3, LCA(3,6)) = DIS(3,1) = $ bd. Similarly, $DIS(6, LCA(3,6)) = DIS(6,1) = $ bx. We can pick subsequence b from both $DIS(3,1)$ and $DIS(6,1)$. After concatenation, we get bb which is a palindrome.

Source: codechef | Difficulty: VERY_HARD
Tags: Graph algorithms

Range queries

Tree algorithms

Dynamic programming

Data structures

Tree queries


Solutions:
import sys
sys.setrecursionlimit(1000000)

def mi():
	return map(int, input().split())

def li():
	return list(mi())

def si():
	return str(input())

def ni():
	return int(input())

def printyes():
	print('YES')

def printno():
	print('NO')

class RangeQuery:

	def __init__(self, data, func=min):
		self.func = func
		self._data = _data = [list(data)]
		(i, n) = (1, len(_data[0]))
		while 2 * i <= n:
			prev = _data[-1]
			_data.append([func(prev[j], prev[j + i]) for j in range(n - 2 * i + 1)])
			i <<= 1

	def query(self, begin, end):
		depth = (end - begin).bit_length() - 1
		return self.func(self._data[depth][begin], self._data[depth][end - (1 << depth)])

class LCA:

	def __init__(self, root, graph):
		self.time = [-1] * len(graph)
		self.path = [-1] * len(graph)
		P = [-1] * len(graph)
		t = -1
		dfs = [root]
		while dfs:
			node = dfs.pop()
			self.path[t] = P[node]
			self.time[node] = t = t + 1
			for nei in graph[node]:
				if self.time[nei] == -1:
					P[nei] = node
					dfs.append(nei)
		self.rmq = RangeQuery((self.time[node] for node in self.path))

	def __call__(self, a, b):
		if a == b:
			return a
		a = self.time[a]
		b = self.time[b]
		if a > b:
			(a, b) = (b, a)
		return self.path[self.rmq.query(a, b)]

def find(g, s, ct, visited, node, n):
	ct[node][ord(s[node - 1]) - 97] += 1
	for i in g[node]:
		if i not in visited:
			visited.add(i)
			for k in range(26):
				ct[i][k] += ct[node][k]
			find(g, s, ct, visited, i, n)
for t in range(int(input())):
	n = ni()
	s = si()
	g = []
	for i in range(n + 1):
		g.append([])
	for i in range(n - 1):
		(a, b) = mi()
		g[a].append(b)
		g[b].append(a)
	L = LCA(1, g)
	visited = set()
	visited.add(1)
	ct = []
	for i in range(n + 5):
		ct.append([0] * 26)
	find(g, s, ct, visited, 1, n)
	for q in range(int(input())):
		(a, b) = mi()
		if a < 1 or b < 1 or a > n or (b > n):
			printno()
			continue
		curr = L(a, b)
		if curr < 1 or curr > n:
			printno()
			continue
		flag = False
		for i in range(26):
			if ct[a][i] - ct[curr][i] > 0 and ct[b][i] - ct[curr][i] > 0:
				flag = True
				break
		if flag:
			printyes()
		else:
			printno()


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

def main():
	import math

	def dfs(u, p, memo, lev, log, g):
		memo[u][0] = p
		for i in range(1, log + 1):
			memo[u][i] = memo[memo[u][i - 1]][i - 1]
		for v in g[u]:
			if v != p:
				lev[v] = lev[u] + 1
				dfs(v, u, memo, lev, log, g)

	def lca(u, v, log, lev, memo):
		if lev[u] < lev[v]:
			(u, v) = (v, u)
		for i in range(log, -1, -1):
			if lev[u] - pow(2, i) >= lev[v]:
				u = memo[u][i]
		if u == v:
			return v
		for i in range(log, -1, -1):
			if memo[u][i] != memo[v][i]:
				u = memo[u][i]
				v = memo[v][i]
		return memo[u][0]
	for _ in range(int(input())):
		n = int(input())

		def helper(node, par, se):
			o = ord(s[node - 1]) - ord('a')
			se[o] += 1
			seen[node] = se[:]
			for nie in g[node]:
				if nie != par:
					helper(nie, node, se[:])
		seen = [set() for _ in range(n + 1)]
		s = list((el for el in input()))
		log = math.ceil(math.log(n, 2))
		g = [[] for i in range(n + 1)]
		memo = [[-1 for i in range(log + 1)] for j in range(n + 1)]
		lev = [0 for i in range(n + 1)]
		for _ in range(n - 1):
			(a, b) = map(int, input().split())
			g[a].append(b)
			g[b].append(a)
		dfs(1, 1, memo, lev, log, g)
		helper(1, -1, [0] * 26)
		for _ in range(int(input())):
			(a, b) = map(int, input().split())
			p = lca(a, b, log, lev, memo)
			f = False
			for j in range(26):
				if f:
					break
				o = seen[a][j] - seen[p][j]
				r = seen[b][j] - seen[p][j]
				if o > 0 and r > 0:
					f = True
			if f:
				print('YES')
			else:
				print('NO')
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


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

def dfs(p, prev, this, lvl):
	level[p] = lvl
	parent[p][0] = prev
	for i in range(1, 21):
		if parent[p][i - 1] != -1:
			parent[p][i] = parent[parent[p][i - 1]][i - 1]
	this[ord(a[p - 1]) - 97] += 1
	count[p] = this[:]
	for i in child[p]:
		if i == prev:
			continue
		dfs(i, p, this[:], lvl + 1)

def lca(u, v):
	if level[u] > level[v]:
		(u, v) = (v, u)
	dist = level[v] - level[u]
	for i in range(20, -1, -1):
		if dist >> i & 1:
			v = parent[v][i]
	if u == v:
		return u
	for i in range(20, -1, -1):
		if parent[u][i] != parent[v][i]:
			u = parent[u][i]
			v = parent[v][i]
	return parent[u][0]

def answer():
	for q in range(int(input())):
		(u, v) = map(int, input().split())
		(Lca, yes) = (lca(u, v), False)
		for i in range(26):
			left = count[u][i] - count[Lca][i]
			right = count[v][i] - count[Lca][i]
			if left >= 1 and right >= 1:
				yes = True
				break
		if yes:
			print('YES')
		else:
			print('NO')
for T in range(int(input())):
	n = int(input())
	a = input().strip()
	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)
	parent = [[-1 for i in range(21)] for j in range(n + 1)]
	level = [0 for i in range(n + 1)]
	count = [None for i in range(n + 1)]
	this = [0 for i in range(26)]
	dfs(1, -1, this, 0)
	answer()