func longestPath(parent []int, s string) (ans int) {
n := len(parent)
g := make([][]int, n)
for i := 1; i < n; i++ {
pa := parent[i]
g[pa] = append(g[pa], i)
}
var dfs func(int) int
dfs = func(x int) (maxLen int) {
for _, y := range g[x] {
len := dfs(y) + 1
if s[y] != s[x] {
ans = max(ans, maxLen+len)
maxLen = max(maxLen, len)
}
}
return
}
dfs(0)
return ans + 1
}
func max(a, b int) int { if b > a { return b }; return a }
class Solution {
List<Integer>[] g;
String s;
int ans;
public int longestPath(int[] parent, String s) {
this.s = s;
var n = parent.length;
g = new ArrayList[n];
Arrays.setAll(g, e -> new ArrayList<>());
for (var i = 1; i < n; i++) g[parent[i]].add(i);
dfs(0);
return ans + 1;
}
int dfs(int x) {
var maxLen = 0;
for (var y : g[x]) {
var len = dfs(y) + 1;
if (s.charAt(y) != s.charAt(x)) {
ans = Math.max(ans, maxLen + len);
maxLen = Math.max(maxLen, len);
}
}
return maxLen;
}
}
class Solution {
public:
int longestPath(vector<int> &parent, string &s) {
int n = parent.size();
vector<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 x) -> int {
int maxLen = 0;
for (int y : g[x]) {
int len = dfs(y) + 1;
if (s[y] != s[x]) {
ans = max(ans, maxLen + len);
maxLen = max(maxLen, len);
}
}
return maxLen;
};
dfs(0);
return ans + 1;
}
};
class Solution:
def longestPath(self, parent: List[int], s: str) -> int:
n = len(parent)
g = [[] for _ in range(n)]
for i in range(1, n):
g[parent[i]].append(i)
ans = 0
def dfs(x: int) -> int:
nonlocal ans
max_len = 0
for y in g[x]:
len = dfs(y) + 1
if s[y] != s[x]:
ans = max(ans, max_len + len)
max_len = max(max_len, len)
return max_len
dfs(0)
return ans + 1
