New update is available. Click here to update.

Same Label Nodes

Posted: 20 Mar, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

You are given a tree having ‘N’ nodes rooted at node 0. Each node has a label. For every node in the tree, your task is to determine the total number of nodes in the current node’s subtree, having the same label as the current node.

Note:

1. All the edges in the given tree are bidirectional.
2. The tree does not contain any cycle or self-loop.
3. A label can only be any lowercase English letter.
Input Format:
The first line contains an integer ‘T’, which denotes the number of test cases to be run.  Then, the ‘T’ test cases follow. 

The first line of each test case contains an integer, ‘N’, denoting the total number of nodes in the tree.

The second line contains a string having ‘N’ characters, where for every, ‘i’ from 0 to ‘N-1’, the ‘i-th’ character denotes the label of the ‘i-th’ node.

Then 'N-1' lines follow. Each line contains two space-separated integers, denoting an edge between these two integers.
Output Format:
For each test case, return an array of size ‘N’, where the ‘i-th’ integer denotes the total number of nodes in the subtree of the ‘(i-1)-th’ node, having the same label as the ‘(i-1)-th’ node.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N <= 10^4

Time Limit: 1sec