相邻字符不同的最长路径

题目

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

---

给你一棵 树（即一个连通、无向、无环图），根节点是节点 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^5
• 对所有 i >= 1 ，0 <= parent[i] <= n - 1 均成立
• parent[0] == -1
• parent 表示一棵有效的树
• s 仅由小写英文字母组成

题解

方法一：

思路

忘记不是二叉树了

思路就是求出每个节点x为根的子树最长路径（路径一端是x）dp[x]。

在x为根的子树中经过节点x的最长路径就是x的儿子节点中前两个最大dp值+1。

整棵树的最长路径肯定在某颗x为根的子树中且经过了x，求出最大值即可。

求子树的最大值和次大值之和，其实只需动态求出前i-1颗子树的最大值mx，然后将第i颗子树的值+mx维护最大值即可。

代码

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