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
27
28
| class Solution {
List<Integer>[] g;
String s;
int ans;
public int longestPath(int[] parent, String s) {
this.s = s;
int n = parent.length;
g = new ArrayList[n];
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 x) {
int maxLen = 0;
for (int y : g[x]) {
int len = dfs(y) + 1;
if (s.charAt(y) != s.charAt(x)) {
ans = Math.max(ans, maxLen + len);
maxLen = Math.max(maxLen, len);
}
}
return maxLen;
}
}
|
wechat
