All Tracks Data Structures Trees Binary/ N-ary Trees Problem

Nodes in a subtree
/

Binary/ N-ary Trees, Data Structures, Depth-first search, Hash function, Tree, 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

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?