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

Обновлено: 2024-03-12
1 мин
[]

Содержание

LeetCode problem 1519

class Solution:
    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:
        def dfs(i, fa):
            res[i] -= cnt[labels[i]]
            cnt[labels[i]] += 1
            for j in g[i]:
                if j != fa:
                    dfs(j, i)
            res[i] += cnt[labels[i]]

        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        cnt = Counter()
        res = [0] * n
        dfs(0, -1)
        return res