Tap here to switch tabs
Problem
Submissions

Problem: Number of Nodes in the Sub-Tree With the Same Label

Try to solve the Number of Nodes in the Sub-Tree With the Same Label problem.

Statement

You are given an integer n representing the number of nodes in a tree rooted at node 00, labeled from 00 to n −1- 1. You are also given a 22D array edges of size n −1- 1, where edges[i] =[ai,bi]= [a_i, b_i] indicates an undirected edge between node aia_i and node bib_i in the tree.

Each node is assigned a character label, given as a string labels where labels[i] is the label of node ii.

Return an array ans of size n, where ans[i] is the number of nodes in the subtree of node ii that have the same label as node ii.

Note: The subtree of a node uu consists of node uu itself along with all of its descendant nodes in the rooted tree.

Constraints:

  • 1≤1 \leq n ≤105\leq 10^5

  • edges.length ==== n −1- 1

  • edges[i].length ==2== 2

  • 0≤ai,bi<0 \leq a_i, b_i < n

  • ai≠bia_i \neq b_i

  • labels.length ==== n

  • labels consists only of lowercase English letters.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Number of Nodes in the Sub-Tree With the Same Label

Try to solve the Number of Nodes in the Sub-Tree With the Same Label problem.

Statement

You are given an integer n representing the number of nodes in a tree rooted at node 00, labeled from 00 to n −1- 1. You are also given a 22D array edges of size n −1- 1, where edges[i] =[ai,bi]= [a_i, b_i] indicates an undirected edge between node aia_i and node bib_i in the tree.

Each node is assigned a character label, given as a string labels where labels[i] is the label of node ii.

Return an array ans of size n, where ans[i] is the number of nodes in the subtree of node ii that have the same label as node ii.

Note: The subtree of a node uu consists of node uu itself along with all of its descendant nodes in the rooted tree.

Constraints:

  • 1≤1 \leq n ≤105\leq 10^5

  • edges.length ==== n −1- 1

  • edges[i].length ==2== 2

  • 0≤ai,bi<0 \leq a_i, b_i < n

  • ai≠bia_i \neq b_i

  • labels.length ==== n

  • labels consists only of lowercase English letters.