1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5int dfs(int node, char *s, int **children, int *children_count, int *max_length) {
6    int first_longest = 0, second_longest = 0;
7    for (int i = 0; i < children_count[node]; i++) {
8        int child = children[node][i];
9        int path_length = dfs(child, s, children, children_count, max_length);
10        if (s[node] != s[child]) {
11            if (path_length > first_longest) {
12                 second_longest = first_longest;
13                 first_longest = path_length;
14            } 
15            else if (path_length > second_longest) {
16                second_longest = path_length;
17            }
18        }
19    }
20    *max_length = fmax(*max_length, first_longest + second_longest + 1);
21    return first_longest + 1;
22}
23
24int longestPath(int* parent, int parentSize, char * s) {
25    int n = parentSize;
26    int **children = (int **)malloc(n * sizeof(int *));
27    int *children_count = (int *)calloc(n, sizeof(int));
28    int max_length = 0;
29
30    for (int i = 0; i < n; i++) {
31        children[i] = (int *)malloc(n * sizeof(int));
32    }
33
34    for (int i = 1; i < n; i++) {
35        children[parent[i]][children_count[parent[i]]++] = i;
36    }
37
38    dfs(0, s, children, children_count, &max_length);
39
40    for (int i = 0; i < n; i++) {
41        free(children[i]);
42    }
43    free(children);
44    free(children_count);
45
46    return max_length;
47}