1using System;
2using System.Collections.Generic;
3
4public class Solution {
5    public int LongestPath(int[] parent, string s) {
6        int n = parent.Length;
7        List<int>[] children = new List<int>[n];
8        for (int i = 0; i < n; i++) {
9            children[i] = new List<int>();
10        }
11        for (int i = 1; i < n; i++) {
12            children[parent[i]].Add(i);
13        }
14        int max_length = 0;
15        Dfs(0, s, children, ref max_length);
16        return max_length;
17    }
18
19    private int Dfs(int node, string s, List<int>[] children, ref int max_length) {
20        int firstLongest = 0, secondLongest = 0;
21        foreach (int child in children[node]) {
22            int pathLength = Dfs(child, s, children, ref max_length);
23            if (s[node] != s[child]) {
24                if (pathLength > firstLongest) {
25                    secondLongest = firstLongest;
26                    firstLongest = pathLength;
27                } else if (pathLength > secondLongest) {
28                    secondLongest = pathLength;
29                }
30            }
31        }
32        max_length = Math.Max(max_length, firstLongest + secondLongest + 1);
33        return firstLongest + 1;
34    }
35}