Problem Statement:

Given a tree (an undirected connected graph with no cycles), each node of which is labeled with a distinct character, you need to count the number of nodes in a subtree with the same label.

Approach:

We can solve this problem using a depth-first search approach. We can traverse the tree using DFS and keep track of the count of characters encountered at each node. We can then return this count of characters to the parent node, where we can merge it with the counts of the different children nodes.

Algorithm:

1. First, we create an adjacency list representation of the given tree, where each node stores its label.

2. Next, we initialize a count map for each character, i.e., for each possible character in the given tree, we create a hashMap and initialize the count of that character to zero.

3. Now, we start traversing the tree using DFS, starting from the root node. For each node, we recursively call the DFS function on all its child nodes.

4. While traversing each child node, we store the count of each character encountered in a temp hashMap.

5. After processing all the child nodes, we add the count of the current node's label to the temp hashMap.

6. We then return the temp hashMap to the parent node.

7. In the parent node, we merge the temp hashMap of all child nodes to get the count of each character in its subtree.

8. We update the global result hashMap with the count of nodes in the current node's subtree with the same label.

9. Finally, we return the count of characters for the current node to its parent.

Pseudo Code:

Initialize the result hashMap

resultHashMap = {}

DFS function

def dfs(node): # Initialize the temp hashMap tempHashMap = {}

# Traverse all child nodes
for child in adjList[node]:
    # Recursively call dfs on the child node
    childHashMap = dfs(child)

    # Update the temp hashMap with the count of characters in child nodes
    for key in childHashMap:
        if key not in tempHashMap:
            tempHashMap[key] = childHashMap[key]
        else:
            tempHashMap[key] += childHashMap[key]

 # Add the count of the current node's character to the temp hashMap
 if nodeLabel in tempHashMap:
     tempHashMap[nodeLabel] += 1
 else:
     tempHashMap[nodeLabel] = 1

 # Update the global result hashMap with the count of nodes in the subtree with the same label
 if nodeLabel in resultHashMap:
     resultHashMap[nodeLabel] += tempHashMap[nodeLabel]
 else:
     resultHashMap[nodeLabel] = tempHashMap[nodeLabel]

# return the temp hashMap to the parent node
return tempHashMap

Call dfs function on the root node

dfs(1)

Print the count of nodes in the subtree with the same label for each node

for node in range(1,n+1): print(resultHashMap[node])

Time Complexity:

The time complexity of the above algorithm is O(n), where n is the number of nodes in the given tree. We traverse each node once and process the count of characters in constant time using a hashMap.

Space Complexity:

The space complexity of the above algorithm is O(n), where n is the number of nodes in the given tree. We use a hashMap to store the count of characters encountered at each node and a hashMap to represent the adjacency list of the tree. Also, we use recursive stack space, which is equivalent to the height of the tree.

1