SOLVE

LATER

Nodes in a subtree

/

You are given a rooted tree that contains **\(N\) **nodes. Each node contains a lowercase alphabet.

You are required to answer **\(Q\) **queries of type \(u, c\), where **\(u\) **is an integer and** \(c\) **is a lowercase alphabet. The count of nodes in the subtree of the node \(u\) containing \(c\) is considered as the answer of all the queries.

**Input format**

- First line: Two space-separated integers
**\(N\ and\ Q\)**respectively - Second line: A string \(s\) of length
**\(N\)**(where the \(i^{th}\) character of \(s\) represents the character stored in node \(i\)) - Next
**\(N - 1\)**line: Two space-separated integers**\(u\)**and**\(v\)**denoting an edge between node**\(u\)**and node \(v\) - Next
**\(Q\)**lines: An integer**\(u\)**and a space-separated character**\(c\)**

**Output format**

For each query, print the output in a new line.

**Constraints**

**\(1 \leq N, Q \leq 10^5\\ 1 \leq u, v \leq N \)**

**\(c\)**is a lowercase alphabet- \(s_i\)
_{ }is a lowercase alphabet for all \(1 \leq i \leq N\) - \(1\) is the root node

**Note**: It is guaranteed that the input generates a valid tree.

Explanation

Tree given in the sample input will look like that.

Number of nodes in the subtree of node 1 having 'a' stored in it is 2.

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...