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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 11:15:09 2023-09-13 11:15:09 Updated    

给你一棵 树 （即一个连通、无向、无环图），根节点是节点 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 仅由小写英文字母组成
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        N = len(parent)
        tree = [[] for i in range(N)]
        for i, p in enumerate(parent[1:], start = 1):
            tree[p].append(i)
        
        # dfs(n): 返回以n为根节点的子树的(最大深度, 次最大深度)
        # 注意:这里计算的深度指的也是无相邻节点分配相同字母的
        @cache
        def dfs(n):
            x = s[n]
            max0 = max1 = 0
            for m in tree[n]:
                if s[m] != x:
                    val = dfs(m)[0]
                    if val > max0:
                        max0, max1 = val, max0
                    elif val > max1:
                        max1 = val
            
            return max0 + 1, max1 + 1
        
        # 找最长的一条路径: 最大深度 + 次最大大深度 - 1(以i节点为根的子树最大深度
        # 和次最大深度中都算入了i,所以会多计算一次, 因此这里要减1)
        return max(sum(dfs(i)) - 1 for i in range(N))
 Comments
On this page
2246-相邻字符不同的最长路径