Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Static Tree

By fsshakkhor · Limits 2s, 512 MB

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 ith character of the string denotes the letter written on the ith 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).


5 4
1 2
1 5
2 3
2 4
3 5 cbb
3 5 bba
5 3 cbb
3 4 cbb

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, Dec '19

peppermintFastest, 0.2s

peppermintLightest, 59 MB

peppermintShortest, 1430B


Login to submit