# 1519. Number of Nodes in the Sub-Tree With the Same Label

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 the node `0`, and each node of the tree has **a label** which is a lower-case character given in the string `labels` (i.e. The node with the number `i` has the label `labels[i]`).

The `edges` array is given on 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 `ith` node which 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:**![](https://assets.leetcode.com/uploads/2020/07/01/q3e1.jpg)

```
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]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).
```

**Example 2:**![](https://assets.leetcode.com/uploads/2020/07/01/q3e2.jpg)

```
Input: n = 4, edges = [[0,1],[1,2],[0,3]], labels = "bbbb"
Output: [4,2,1,1]
Explanation: The sub-tree of node 2 contains only node 2, so the answer is 1.
The sub-tree of node 3 contains only node 3, so the answer is 1.
The sub-tree of node 1 contains nodes 1 and 2, both have label 'b', thus the answer is 2.
The sub-tree of node 0 contains nodes 0, 1, 2 and 3, all with label 'b', thus the answer is 4.
```

**Example 3:**![](https://assets.leetcode.com/uploads/2020/07/01/q3e3.jpg)

```
Input: n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = "aabab"
Output: [3,2,1,1,1]
```

**Example 4:**

```
Input: n = 6, edges = [[0,1],[0,2],[1,3],[3,4],[4,5]], labels = "cbabaa"
Output: [1,2,1,1,2,1]
```

**Example 5:**

```
Input: n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6]], labels = "aaabaaa"
Output: [6,5,4,1,3,2,1]
```

**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 lower-case English letters.

对树上每个结点统计它和它子树上与它的值相同的结点数目，值范围为\[a, z]。树非按层统计结点=>DFS/分治。假设每个子节点对应的树对每个值在该子树的频次已经统计完毕，将频率汇总并对该结点的值频次加一，返回。

```python
class Solution:
    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:
        g, res = collections.defaultdict(list), [0] * n
        for (a, b) in edges:
            g[a].append(b)
            g[b].append(a)
        def dfs(i, last, g, labels, res):
            cnt = collections.Counter()
            for nei in g[i]:
                if nei == last: continue
                cnt += dfs(nei, i, g, labels, res)
            cnt[labels[i]] += 1
            res[i] = cnt[labels[i]]
            return cnt

        dfs(0, -1, g, labels, res)
        return res
            
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/binary_tree_and_divide_conquer/1519.-number-of-nodes-in-the-sub-tree-with-the-same-label.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.