leetcode

0 class Solution {

1 public:

2 int longestPath(vector<int> &parent, string s) {

3 int n = parent.size();

4

5 vector<vector<int>> adj(n);

6 vector<int> pc(n, 0), count(n);

7 for (int i = 1; i < n; i++)

8 pc[parent[i]]++;

9

10 queue<int> q;

11 for (int i = 0; i < n; i++)

12 if (pc[i] == 0) q.push(i);

13

14 int res = 0;

15 while (true) {

16 int crnt = q.front();

17 q.pop();

18

19 int mx1 = 0, mx2 = 0;

20 for (int c : adj[crnt]) {

21 int a = s[crnt] != s[c] ? count[c] : 0;

22 if (a > mx1) {

23 mx2 = mx1;

24 mx1 = a;

25 } else if (a > mx2) {

26 mx2 = a;

27 }

28 }

29 res = max(res, mx1 + mx2 + 1);

30 count[crnt] = mx1 + 1;

31

32 if (crnt == 0) break;

33 int p = parent[crnt];

34 adj[p].push_back(crnt);

35 if (!--pc[p]) q.push(p);

36 }

37

38 return res;

39 }

40 };