2246. 相邻字符不同的最长路径

来源第 289 场周赛 Q4难度困难分数2126

题目描述

给你一棵树（即一个连通、无向、无环图），根节点是节点 0 ，这棵树由编号从 0 到 n - 1 的 n 个节点组成。用下标从 0 开始、长度为 n 的数组 parent 来表示这棵树，其中 parent[i] 是节点 i 的父节点，由于节点 0 是根节点，所以 parent[0] == -1 。

另给你一个字符串 s ，长度也是 n ，其中 s[i] 表示分配给节点 i 的字符。

请你找出路径上任意一对相邻节点都没有分配到相同字符的 最长路径 ，并返回该路径的长度。

示例 1：

输入：parent = [-1,0,0,1,1,2], s = "abacbe"
输出：3
解释：任意一对相邻节点字符都不同的最长路径是：0 -> 1 -> 3 。该路径的长度是 3 ，所以返回 3 。
可以证明不存在满足上述条件且比 3 更长的路径。

示例 2：

输入：parent = [-1,0,0,0], s = "aabc"
输出：3
解释：任意一对相邻节点字符都不同的最长路径是：2 -> 0 -> 3 。该路径的长度为 3 ，所以返回 3 。

提示：

n == parent.length == s.length
1 <= n <= 10⁵
对所有 i >= 1 ，0 <= parent[i] <= n - 1 均成立
parent[0] == -1
parent 表示一棵有效的树
s 仅由小写英文字母组成

解法

方法一：树形 DP

思考

在树上找一条相邻字符均不同的最长路径。 \(n \le 10^5\)，不能枚举端点对。路径要么完全落在某一子树，要么在某点处把两条合法向下链拼起来。

DFS 返回「从当前点向下、且第一步字符不同」的最长链长。对每个儿子先递归；仅当 \(s[i]\neq s[j]\) 时，用当前次长链与这条新链更新全局答案，并维护最长向下链。根上再加一（计入自身）。一次遍历即可。

我们先根据数组 \(parent\) 构建邻接表 \(g\)，其中 \(g[i]\) 表示节点 \(i\) 的所有子节点。

然后我们从根节点开始 DFS，对于每个节点 \(i\)，我们遍历 \(g[i]\) 中的每个子节点 \(j\)，如果 \(s[i] \neq s[j]\)，那么我们就可以从 \(i\) 节点出发，经过 \(j\) 节点，到达某个叶子节点，这条路径的长度为 \(x = 1 + dfs(j)\)，我们用 \(mx\) 记录最长的一条从节点 \(i\) 出发的路径长度。同时，在遍历的过程中，更新答案 \(ans = \max(ans, mx + x)\)。

最后，我们返回 \(ans + 1\) 即可。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为节点个数。

Python3JavaC++GoTypeScript

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

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

class Solution {
    private List<Integer>[] g;
    private String s;
    private int ans;

    public int longestPath(int[] parent, String s) {
        int n = parent.length;
        g = new List[n];
        this.s = s;
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int i = 1; i < n; ++i) {
            g[parent[i]].add(i);
        }
        dfs(0);
        return ans + 1;
    }

    private int dfs(int i) {
        int mx = 0;
        for (int j : g[i]) {
            int x = dfs(j) + 1;
            if (s.charAt(i) != s.charAt(j)) {
                ans = Math.max(ans, mx + x);
                mx = Math.max(mx, x);
            }
        }
        return mx;
    }
}

class Solution {
public:
    int longestPath(vector<int>& parent, string s) {
        int n = parent.size();
        vector<int> g[n];
        for (int i = 1; i < n; ++i) {
            g[parent[i]].push_back(i);
        }
        int ans = 0;
        function<int(int)> dfs = [&](int i) -> int {
            int mx = 0;
            for (int j : g[i]) {
                int x = dfs(j) + 1;
                if (s[i] != s[j]) {
                    ans = max(ans, mx + x);
                    mx = max(mx, x);
                }
            }
            return mx;
        };
        dfs(0);
        return ans + 1;
    }
};

func longestPath(parent []int, s string) int {
    n := len(parent)
    g := make([][]int, n)
    for i := 1; i < n; i++ {
        g[parent[i]] = append(g[parent[i]], i)
    }
    ans := 0
    var dfs func(int) int
    dfs = func(i int) int {
        mx := 0
        for _, j := range g[i] {
            x := dfs(j) + 1
            if s[i] != s[j] {
                ans = max(ans, x+mx)
                mx = max(mx, x)
            }
        }
        return mx
    }
    dfs(0)
    return ans + 1
}

function longestPath(parent: number[], s: string): number {
    const n = parent.length;
    const g: number[][] = Array.from({ length: n }, () => []);
    for (let i = 1; i < n; ++i) {
        g[parent[i]].push(i);
    }
    let ans = 0;
    const dfs = (i: number): number => {
        let mx = 0;
        for (const j of g[i]) {
            const x = dfs(j) + 1;
            if (s[i] !== s[j]) {
                ans = Math.max(ans, mx + x);
                mx = Math.max(mx, x);
            }
        }
        return mx;
    };
    dfs(0);
    return ans + 1;
}

方法二：树形 DP + 显式栈

思考

在树上找一条相邻字符均不同的最长路径。 \(n \le 10^5\)，从根递归求每棵子树的向下链，链上的调用深度就是 \(n\)，会超出递归栈。

这样的路径要么完全落在某一子树，要么在某个点把两条向下链拼起来。离开一个节点时，儿子的向下链已经知道：仅当 \(s[i] \neq s[j]\) 时，这条链才能接到 \(i\) 上，长度是儿子的链长加 \(1\)。用当前最长的一条与新链更新全局答案，并留下更长的那条作为本节点的向下链。

显式栈按 \((节点, 状态)\) 做后序。进入时先压出栈标记再压孩子，离开时按上面的规则更新答案和向下链。最后把答案加 \(1\)，补上路径经过的节点数。