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 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).

Input | Output |
---|---|

5 6 abcbb 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 | Yes No No Yes No |

71% Solution Ratio

dip_BRUREarliest,

samiulsamiFastest, 0.3s

Nafis_ShhriarLightest, 106 MB

borderShortest, 6244B

Login to submit

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