Substrings on a Tree

All submissions for this problem are available.
Chefland scientists have made a new invention! They developed a new way to represent a string with N symbols: consider a tree with N vertices, rooted at the first vertice. For each vertice, a single latin letter is written. So we have obtained a "treestring". The scientists haven't decided yet how the treestring should be pronounced, but they have invented a definition of a substring for a treestring. A string is a substring of a treestring if and only it can be obtained by moving from some vertice to its descendant and writing out all the letters from vertices that occured on this path in the order they have appeared. For example, consider the following treestring :
The string "ba" is a substring of a given treestring because it can be obtained by moving from vertice 4 to vertice 6, the string "abb" is also a substring of this treestring  it can be obtained by moving from the root to vertice 5. However the string "cb" is not a substring of this treestring because there is no way from any vertice to its descendant in such a way that the sequence of letters is "cb".
Now the Chefland researchers ask you to help them with the treestring research.
They have given you a treestring with N vertices.
Please output the number of distinct substrings of a given treestring (including the empty one).
Then, Q queries will follow.
For the ith query, the permutation P_{i} of 26 latin alphabet letters and an integer K_{i} will be given.
That means that if we sort all distinct substrings of the given treestring according to the alphabetical order described in P_{i}, you will have to output the K_{i}th string.
"According to the alphabetical order described in P_{i}" means that letter X is lexicographically smaller that letter Y if and only X appears
in P_{i} earlier than Y. For example if the alphabetical order is "cbadefghijklmnopqrstuvwxyz", then letter "c" is lexicographically smaller than letter "a" because "c" is the first symbol of this permutation, and "a" is the third symbol of this permutation, therefore 1<3 and for the given arrangement, "c" is alphabetically less than "a".
Here note that the string A is smaller than the string B (that means A comes earlier than B
after sorting) if and only if
A is a prefix of B,
or A_{i} = B_{i} (for all i < k) and A_{k} < B_{k} (in terms of alphabetical order)
where A_{i} denotes the ith letter of A.
Constraints
 1<=N<=250000
 1<=Q<=50000
 1<=K_{i}<=9223372036854775807 (2^631)
 Output will not exceed 800 KB.
 It is guaranteed that the N lowercase latin letters have been generated randomly.
Input
The first line of input consists of two integers  N and Q.
Then, a string composed of N lowercase latin letters follow.
Then, N1 lines follow. Each line is composed of two numbers  X_{i} and Y_{i}. It means that there is an edge between vertice X_{i} and vertice Y_{i}.
Then, Q lines follow. Each line consists of a permutation of 26 lowercase latin letters P_{i} and an integer K_{i}.
Output
Output Q+1 lines. On the first line output a single integer  the number of distinct substrings of a given treestring. The following Q lines should contain answers to the queries. Ith line should contain an answer to ith query or a string "1" if it is impossible
to find K_{i}th string for ith query.
Example
Input: 8 4 abcbbaca 1 2 2 3 1 4 4 5 4 6 4 7 1 8 abcdefghijklmnopqrstuvwxyz 5 abcdefghijklmnopqrstuvwxyz 1 bcadefghijklmnopqrstuvwxyz 5 abcdefghijklmnopqrstuvwxyz 100 Output: 12 aba ba 1
Author:  xcwgf666 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/TSUBSTR 
Tags  april12, hard, xcwgf666 
Date Added:  1032012 
Time Limit:  0.514221 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions