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]
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] to node D[i] using the shortest possible path.
Let V, V...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.
I <= A <= 10 ^ 5
B is a matrix of dimensions (A — 1) * 2
Feel free to share aprroaches Thanks in Advance
1<=B[i] , B[i] <= A
length(C) = A
Conly contains lowercase english alphabets
1 <= Q <= 10 ^ 5
D is a matrix of dimensions Q * 2