Nodes in a subtree

2.2

57 votes
Binary Tree, Data Structures, Depth First Search, Easy, Hash Maps, Trees
Problem

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 ith character of s represents the character stored in node i)
  • Next N1 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

1N,Q1051u,vN

  • c is a lowercase alphabet
  • si is a lowercase alphabet for all 1iN
  • 1 is the root node

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

Time Limit: 1
Memory Limit: 256
Source Limit:
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. 

Editor Image

?