Problem Description
You love strings a lot, so you decided to play the following game.
You have a tree T of A nodes. The tree is represented by a matrix B of dimensions (A — 1) * 2 such that there exist an edge between node B[i]|1| and B[i][2]
Each node is assigned a lowercase english character, which is represented by a string C of length A. Node is assigned character at position i of string C. You are given Q queries in the form of a matrix D of dimensions Q * 2 For each you query you will perform the following steps:
You will move from node p[i][1] to node D[i][2] using the shortest possible path.
Let V[1], V[2]...V[K] be the nodes visited in the corresponding order. Create a string $ such that length of S is equal to K and S[i]=c[v|i]]
Store string S in your bag.
Return the number of unique strings you would create.
Problem Constraints
I <= A <= 10 ^ 5
B is a matrix of dimensions (A — 1) * 2
Feel free to share aprroaches Thanks in Advance
1<=B[i][1] , B[i][2] <= A
length(C) = A
Conly contains lowercase english alphabets
1 <= Q <= 10 ^ 5
D is a matrix of dimensions Q * 2
1<=D[i][1],D[i][2]<=A
