1519. 子树中标签相同的节点数

题目描述

给了一些点的连通关系，每个点的值都不同，每个点上都哟一个附加的标签（小写字母）
问：每个节点i的子树中标签和i相同的节点数

基本分析

1. 怎么根据连接关系进行遍历？先建图
2. 遍历的时候没有方向，怎么保证不会回去？加一个父节点的参数，保证不会往前走？
3. 怎么维护当前节点的信息？（1）遍历顺序？后序遍历，子节点信息拿到以后，在维护当前节点信息；（2）什么结构？需要f[i][j]表示节点i的第j个字母（0-'a', 1-'b',25-'z'）的出现次数；（3）怎么维护？每个子节点dfs之后，这个节点的信息已知了，[cur]...+= [y]...
4. 怎么拿到答案？从f中拿出和当前节点标签相同的点拼起来。

代码

class Solution:
    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:
        
        f = [[0]*26 for _ in range(n)]

        g = defaultdict(list)
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)
        
        def dfs(cur, par):
            # 维护当前节点子树中字符的情况
            f[cur][ord(labels[cur]) - ord('a')] += 1
            # 枚举子节点
            for y in g[cur]:
                # 保证不往上跑
                if y != par:
                    dfs(y, cur)
                    for i in range(26):
                        f[cur][i] += f[y][i]

        dfs(0, -1)

        ans = [f[i][ord(labels[i]) - ord('a')] for i in range(n)]

        return ans

总结

1. 利用edges建图
2. dfs时候利用par参数保证不往回走
3. 后序遍历，子节点dfs之后，可以认为子节点信息已知，利用以上信息维护当前节点信息