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

Условие: дано дерево (т.е. связанный неориентированный граф, не имеющий циклов) с корнем в узле 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

Решение: Go

Сложности

• Временная : O(n)
• Пространственная : O(n)

Code

func longestPath(parent []int, s string) int {
    maxLength := 0
    n := len(parent)

    children := make([][]int, n)
    for i, pi := range parent {
        if pi == -1 {
            continue
        }
        children[pi] = append(children[pi], i)
    }

    dfs(0, children, s, &maxLength)
    return maxLength
}

func dfs(curNode int, children [][]int, s string, maxLength *int) int {
    maxPath1, maxPath2 := 0, 0
    for _, child := range children[curNode] {
        l := dfs(child, children, s, maxLength)
        if s[curNode] != s[child] {
            if l >= maxPath1 {
                maxPath2 = maxPath1
                maxPath1 = l
            } else if l > maxPath2 {
                maxPath2 = l
            }
        }
    }
    *maxLength = max(*maxLength, maxPath1+maxPath2+1)
    return maxPath1+1
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}