2246. Longest Path With Different Adjacent Characters

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        def dfs(i: int) -> int:
            mx = 0
            nonlocal res
            for j in g[i]:
                x = dfs(j) + 1
                if s[i] != s[j]:
                    res = max(res, mx + x)
                    mx = max(mx, x)
            return mx

        g = defaultdict(list)
        for i in range(1, len(parent)):
            g[parent[i]].append(i)
        res = 0
        dfs(0)
        return res + 1