Tap here to switch tabs
Problem
Submissions

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

Number of Nodes in the Sub-Tree With the Same Label asks you to return, for every tree node, how many nodes in its rooted subtree share that node’s character label.

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

Number of Nodes in the Sub-Tree With the Same Label asks you to return, for every tree node, how many nodes in its rooted subtree share that node’s character label.

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.