Number of Nodes in the Sub-Tree With the Same Label
You are given a tree (i.e. a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. The root of the tree is node 0, and each node of the tree has a label, which is a lowercase character given in the string labels; the node with number i has the label labels[i].
The edges array is given in the form edges[i] = [ai, bi], which means there is an edge between nodes ai and bi in the tree.
Return an array of size n where ans[i] is the number of nodes in the subtree of the i^th node that have the same label as node i.
A subtree of a tree T is the tree consisting of a node in T and all of its descendant nodes.
Example 1
Input
n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"Output
[2,1,1,1,1,1,1]Node 0 has label 'a' and its subtree also contains node 2 with label 'a', while every other node has only itself with the same label in its subtree.
Example 2
Input
n = 4, edges = [[0,1],[1,2],[0,3]], labels = "bbbb"Output
[4,2,1,1]All labels are 'b', so each node's answer is the size of its subtree: node 0 has 4 nodes, node 1 has 2 nodes, and nodes 2 and 3 each have 1 node.
Constraints
- 1 <= n <= 10^5
- edges.length == n - 1
- edges[i].length == 2
- 0 <= ai, bi < n
- ai != bi
- labels.length == n
- labels is consisting of only of lowercase English letters.