- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Suppose we have a rooted general tree with n nodes, whose nodes are numbered from 0 to n-1. Each node has a label with lowercase English letter. The labels are given as input in labels array, where lables[i] contains label for ith node. The tree is represented by edge list where each edge e has [u,v] represents u is parent and v is child. We have to find an array A of size n, represents number of nodes in the subtree of the ith node with same label as i

So, if the input is like

Here n = 5 and label = “ccaca”

then the output will be [3, 2, 1, 1, 1] as the root has three descendants with same label, node 1 has two descendants, and all other itself holding that label.

To solve this, we will follow these steps −

E := Make graph from the given edge list

N := a map containing each node number and its corresponding label

R := a list of size n and fill with 0

Define a function r() . This will take ni

C := a map to hold frequency of a key

for each e in E[ni], do

delete ni from E[e]

update r(e) in C

update N[ni] in C

R[ni] := C[N[ni]]

return C

From the main method call r(0)

return R

Let us see the following implementation to get better understanding −

from collections import defaultdict, Counter def solve(n, edges, labels): E = defaultdict(set) for f,t in edges: E[f].add(t) E[t].add(f) N = {i:e for i,e in enumerate(labels)} R = [0]*n def r(ni): C = Counter() for e in E[ni]: E[e].remove(ni) C.update(r(e)) C.update((N[ni])) R[ni] = C[N[ni]] return C r(0) return R n = 5 edges = [[0,1],[0,2],[1,3],[0,4]] labels = "ccaca" print(solve(n, edges, labels))

5, [[0,1],[0,2],[1,3],[0,4]], "ccaca"

[3, 2, 1, 1, 1]

- Related Questions & Answers
- Python Program to Find the Sum of all Nodes in a Tree
- Program to find number of sub-arrays with odd sum using Python
- Python Program to Find the Sum of All Nodes in a Binary Tree
- Python Program to Display the Nodes of a Tree using BFS Traversal
- Program to Find Out the Special Nodes in a Tree in Python
- Program to find out the lowest common ancestor of a binary tree of given nodes using Python
- XOR of all the nodes in the sub-tree of the given node in C++
- Program to find number of good leaf nodes pairs using Python
- Program to find the largest sum of the path between two nodes in a binary tree in Python
- Program to find minimum number of vertices to reach all nodes using Python
- Python Program to Count Number of Non Leaf Nodes of a given Tree
- Program to print nodes in the Top View of Binary Tree using C++
- Program to find number of nodes in a range in Python
- Program to find longest path between two nodes of a tree in Python
- Program to find maximum sum of non-adjacent nodes of a tree in Python

Advertisements