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

题解

题目：给一棵树的每个节点赋一个字符，求一个最长路径，相邻节点的字符不能一样

思路：

1. 路径为 t1 <- target -> t2
2. t1和t2可以为零
3. 枚举target
4. 用dfs枚举所有情况

代码

func longestPath(parent []int, s string) (ans int) {
          
   
	n := len(parent)
	//key 父节点 val 子节点，存图
	g := make(map[int][]int)
	for i := 1; i < n; i++ {
          
   
		fa := parent[i]
		g[fa] = append(g[fa], i)
	}
	var dfs func(x int) (tLen int)
	dfs = func(x int) (maxLen int) {
          
   
		//最长，次长
		fstLong, scdLong := 0, 0
		//遍历所有子节点
		for _, y := range g[x] {
          
   
			subLong := dfs(y)
			//相邻节点字符不相等
			if s[x] != s[y] {
          
   
				if subLong > fstLong {
          
   
					scdLong = fstLong
					fstLong = subLong
				} else if subLong > scdLong {
          
   
					scdLong = subLong
				}
			}
		}
		//更新答案，路径长=最长+次长+本节点1
		ans = max(ans, fstLong+scdLong+1)
		//返回当前节点下的最长路径+本身这个节点1
		return fstLong + 1
	}
	dfs(0)
	return ans
}

func max(a, b int) int {
          
   
	if b > a {
          
   
		return b
	}
	return a
}