1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int longestPath(vector<int>& parent, string s) {
int n = parent.size();
vector<vector<int>> g(n, vector<int>());
for (int i = 1; i < n; ++i) {
g[parent[i]].emplace_back(i);
}
int ans = 0;
function<int(int)> dfs = [&](int u) {
int maxLen = 0;
for (int v : g[u]) {
int len = dfs(v) + 1;
if (s[v] != s[u]) {
ans = max(ans, maxLen + len);
maxLen = max(maxLen, len);
}
}
return maxLen;
};
dfs(0);
return ans + 1;
}
};
|