Longest Path With Different Adjacent Characters

class Solution {
public:
    int longestPath(vector<int>& parent, string s) {
        int n = parent.size();
        vector<vector<int>> children(n);
        for (int i = 1; i < n; ++i) children[parent[i]].push_back(i);
        int best = 1;
        function<int(int)> dfs = [&](int u) -> int {
            int top1 = 0, top2 = 0;
            for (int v : children[u]) {
                int chainLen = dfs(v);
                if (s[v] == s[u]) continue;
                if (chainLen > top1) { top2 = top1; top1 = chainLen; }
                else if (chainLen > top2) top2 = chainLen;
            }
            best = max(best, top1 + top2 + 1);
            return top1 + 1;
        };
        dfs(0);
        return best;
    }
};

func longestPath(parent []int, s string) int {
    n := len(parent)
    children := make([][]int, n)
    for i := 1; i < n; i++ {
        children[parent[i]] = append(children[parent[i]], i)
    }
    best := 1
    var dfs func(u int) int
    dfs = func(u int) int {
        top1, top2 := 0, 0
        for _, v := range children[u] {
            chainLen := dfs(v)
            if s[v] == s[u] {
                continue
            }
            if chainLen > top1 {
                top2 = top1
                top1 = chainLen
            } else if chainLen > top2 {
                top2 = chainLen
            }
        }
        if top1+top2+1 > best {
            best = top1 + top2 + 1
        }
        return top1 + 1
    }
    dfs(0)
    return best
}

from typing import List

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        n = len(parent)
        children: List[List[int]] = [[] for _ in range(n)]
        for i in range(1, n):
            children[parent[i]].append(i)
        best = 1

        def dfs(u: int) -> int:
            nonlocal best
            top1, top2 = 0, 0
            for v in children[u]:
                chain_len = dfs(v)
                if s[v] == s[u]:
                    continue
                if chain_len > top1:
                    top2 = top1
                    top1 = chain_len
                elif chain_len > top2:
                    top2 = chain_len
            best = max(best, top1 + top2 + 1)
            return top1 + 1

        dfs(0)
        return best

function longestPath(parent, s) {
    const n = parent.length;
    const children = Array.from({ length: n }, () => []);
    for (let i = 1; i < n; i++) children[parent[i]].push(i);
    let best = 1;
    const dfs = (u) => {
        let top1 = 0, top2 = 0;
        for (const v of children[u]) {
            const chainLen = dfs(v);
            if (s[v] === s[u]) continue;
            if (chainLen > top1) { top2 = top1; top1 = chainLen; }
            else if (chainLen > top2) top2 = chainLen;
        }
        best = Math.max(best, top1 + top2 + 1);
        return top1 + 1;
    };
    dfs(0);
    return best;
}

class Solution {
    private List<List<Integer>> children;
    private String s;
    private int best;

    public int longestPath(int[] parent, String s) {
        int n = parent.length;
        this.s = s;
        children = new ArrayList<>();
        for (int i = 0; i < n; i++) children.add(new ArrayList<>());
        for (int i = 1; i < n; i++) children.get(parent[i]).add(i);
        best = 1;
        dfs(0);
        return best;
    }

    private int dfs(int u) {
        int top1 = 0, top2 = 0;
        for (int v : children.get(u)) {
            int chainLen = dfs(v);
            if (s.charAt(v) == s.charAt(u)) continue;
            if (chainLen > top1) {
                top2 = top1;
                top1 = chainLen;
            } else if (chainLen > top2) {
                top2 = chainLen;
            }
        }
        best = Math.max(best, top1 + top2 + 1);
        return top1 + 1;
    }
}

function longestPath(parent: number[], s: string): number {
    const n = parent.length;
    const children: number[][] = Array.from({ length: n }, () => []);
    for (let i = 1; i < n; i++) children[parent[i]].push(i);
    let best = 1;
    const dfs = (u: number): number => {
        let top1 = 0, top2 = 0;
        for (const v of children[u]) {
            const chainLen = dfs(v);
            if (s[v] === s[u]) continue;
            if (chainLen > top1) { top2 = top1; top1 = chainLen; }
            else if (chainLen > top2) top2 = chainLen;
        }
        best = Math.max(best, top1 + top2 + 1);
        return top1 + 1;
    };
    dfs(0);
    return best;
}