Last Updated: 20 Mar, 2021

Same Label Nodes

Easy

Asked in companies

Solve now

Problem statement

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

Solve now

Approaches

01 Approach

The approach is to use Depth First Search. We can observe that the number of nodes in the subtree of the current node having the same label as the current node is equal to the total sum of the number of such nodes in each of the current node’s children. We can add 1 to this sum as the current node is also a part of the subtree. For each node, we can maintain a list of the frequencies of each character in the subtree of that node. We can avoid repetitions by keeping a track of all the nodes that we have already VISITED.

Steps

Initialize a vector, say SAME_LABEL_NODES to store the required values for each node. Initially, all the values must be 0.
Initialize a vector of adjacency lists, say TREE for all nodes.
Run a loop for i = 0 to i = EDGES.size and:
1. Declare NODE1 = EDGES[i][0] and NODE2 = EDGES[i][1].
2. Push NODE1 in TREE[NODE2] and push NODE2 in TREE[NODE1].
Initialize a boolean vector, say VISITED to keep track of whether a node has already been VISITED or not. Initially, all values must be false.
Call the function COUNT_FREQUENCIES(TREE, LABELS, 0, VISITED, SAME_LABEL_NODES). For every node, this function will count frequencies of each letter in the subtree of this node and store all the required values in SAME_LABEL_NODES.
Finally, we can return SAME_LABEL_NODES.

vector<int> COUNT_FREQUENCIES(TREE, LABELS, CURR_NODE, VISITED, SAME_LABEL_NODES)

Make VISITED[CURR_NODE] = true.
Create a vector, say CURR_NODE_FREQ to store frequencies in the subtree of CURR_NODE.
Run a loop for i=0 to i=TREE[CURR_NODE].size and do:
1. Declare CHILDE_NODE = TREE[CURR_NODE][i].
2. If CHILDE_NODE has already been VISITED, continue.
3. Create a vector, say CHILDE_NODE_FREQ to store the result of COUNT_FREQUENCIES(TREE, LABELS, CHILDE_NODE, VISITED, SAME_LABEL_NODES).
4. Now, for every letter, add its frequency in the CHILDE_NODE to the corresponding frequency in the CURR_NODE_FREQ. Formally, for every k=0 to k=2 make CURR_NODE_FREQ[k] += CHILDE_NODE_FREQ[k].
5. Increase the frequency of the current node’s label in CURR_NODE_FREQ by 1.
6. Since the required value for the current node is equal to the frequency of this label in the subtree of the current node, make SAME_LABEL_NODES[CURR_NODE] = CURR_NODE_FREQ[LABELS[CURR_NODE] - 'a'].
7. Return CURR_NODE_FREQ.

Solve now