Practice on Toph

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

Dynamic 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 have to perform Q operations on the tree. There are two types of operations:

1. Update: You will be given a vertex U and a character C. You will update the character written on vertex U with C.

2. 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 contains two integers A(1 ≤ A ≤ N) and B(1 ≤ B ≤ N), denoting the edges of the tree.

In the next Q lines each, it will contain an integer TYPE, denoting the type of the operation.

If TYPE = 1, the line will contain an integer U(1 ≤ U ≤ N) and a lowercase English character C.

If TYPE = 2, the line will 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 length of S in all queries of type 2 will not exceed 1000000.


For each query of TYPE 2, print "Yes" (without quotation marks) if S is a subsequence of T. Otherwise, print "No" (without quotation marks).


5 6
1 2
1 5
2 3
2 4
2 3 5 cbb
2 3 5 bba
2 5 3 cbb
2 3 4 cbb
1 2 a
2 3 4 cbb



71% Solution Ratio

dip_BRUREarliest, Dec '19

samiulsamiFastest, 0.3s

Nafis_ShhriarLightest, 106 MB

borderShortest, 6244B


Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.