Question

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

English Version

题目描述

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

解法

方法一：树形 DP

我们先根据数组 $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$ 为节点个数。

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;
}