Задача: Самый длинный путь с разными соседними символами

Условие: дано дерево (т.е. связанный неориентированный граф, не имеющий циклов) с корнем в узле 0, состоящее из n узлов, пронумерованных от 0 до n - 1. Дерево представлено родительским массивом с индексом 0 размера n, где родительский элемент[i] является родительским элементом узла i. Поскольку узел 0 является корневым, родительский элемент[0] == -1.

Вам также выдаются строки длиной n, где s[i] - символ, присвоенный узлу i.

Возвращает длину самого длинного пути в дереве таким образом, чтобы ни одной паре соседних узлов пути не был присвоен один и тот же символ.

Пример:

Ввод: parent = [-1,0,0,1,1,2], s = "abacbe"

Вывод: 3

Ввод: parent = [-1,0,0,0], s = "aabc"

Вывод: 3

Решение: Python

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        t={}
        for i in range(1,len(parent)):
            if parent[i] not in t:
                t[parent[i]]=[i]
            else:
                t[parent[i]].append(i)
            
        self.ans=1
        def fun(i):
            if i not in t:
                return 1
            res = 1
            for j in t[i]:
                length=fun(j)
                if s[i] != s[j]:
                    self.ans = max(self.ans,length+res)
                    res = max(res,length+1)
            return res
        
        fun(0)
        return self.ans