Practice on Toph
Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.
Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.
You are given a tree containing N vertices. The vertices are numbered from 1 to N. A tree with N vertices is an undirected connected graph with exactly N−1 edges. Each vertex of the tree contains a lowercase English letter.
You will be asked Q queries. In each query, you will be given two integers U and V, denoting two vertices of the tree and a string S containing lowercase English letters. You will build a new string T by writing down the letters sequentially which are in vertices of the simple path from U to V. You have to say whether S is a subsequence of T or not.
Recall that, the subsequence of the string A is a string B that can be obtained from A by removing some (possibly zero) amount of characters.
The first line contains two integers N (1 ≤ N ≤ 200000) and Q (1 ≤ Q ≤ 200000).
The next line contains a string of length N. The i^{th} character of the string denotes the letter written on the i^{th} vertex. It is guaranteed that all the characters of the string are lowercase English letters.
Each of the next N-1 lines contain two integers A(1 ≤ A ≤ N) and B(1 ≤ B ≤ N), denoting the edges of the tree.
Each of the next Q lines contain two integers U(1 ≤ U ≤ N) and V(1 ≤ V ≤ N) and a string S(1 ≤ |S| ≤ 200000) containing lowercase English letters.
It is guaranteed that the sum of lengths of S in all queries will not exceed 1000000.
For each query, print "Yes" (without quotation marks) if S is a subsequence of T. Otherwise, print "No" (without quotation marks).
Input | Output |
---|---|
5 4 abcbb 1 2 1 5 2 3 2 4 3 5 cbb 3 5 bba 5 3 cbb 3 4 cbb | Yes No No Yes |
Query 1: From the path (3 -> 2 -> 1 -> 5), we get T = cbab, which contains cbb as a subsequence. Query 2: From the path (3 -> 2 -> 1 -> 5), we get T = cbab. bba is not a subsequence of cbab. Query 3: From the path (5 -> 1 -> 2 -> 3), we get T = babc. cbb is not a subsequence of babc. Query 4: From the path (3 -> 2 -> 4), we get T = cbb, which contains cbb as a subsequence. |
82% Solution Ratio
sarthakmannaEarliest,
peppermintFastest, 0.2s
peppermintLightest, 59 MB
peppermintShortest, 1430B
Login to submit