Nodes in a subtree
/

## Binary Tree, Data Structures, Depth First Search, Hash Maps, Trees

Problem
Editorial
Analytics

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.

SAMPLE INPUT
3 1
aba
1 2
1 3
1 a
SAMPLE OUTPUT
2

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

## This Problem was Asked in

Initializing Code Editor...