<p>You are given a <strong>tree</strong> (i.e. a connected, undirected graph that has no cycles) <strong>rooted</strong> at node <code>0</code> consisting of <code>n</code> nodes numbered from <code>0</code> to <code>n - 1</code>. The tree is represented by a <strong>0-indexed</strong> array <code>parent</code> of size <code>n</code>, where <code>parent[i]</code> is the parent of node <code>i</code>. Since node <code>0</code> is the root, <code>parent[0] == -1</code>.</p>

<p>You are also given a string <code>s</code> of length <code>n</code>, where <code>s[i]</code> is the character assigned to node <code>i</code>.</p>

<p>Return <em>the length of the <strong>longest path</strong> in the tree such that no pair of <strong>adjacent</strong> nodes on the path have the same character assigned to them.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/03/25/testingdrawio.png" style="width: 201px; height: 241px;" />
<pre>
<strong>Input:</strong> parent = [-1,0,0,1,1,2], s = &quot;abacbe&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong> The longest path where each two adjacent nodes have different characters in the tree is the path: 0 -&gt; 1 -&gt; 3. The length of this path is 3, so 3 is returned.
It can be proven that there is no longer path that satisfies the conditions. 
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/03/25/graph2drawio.png" style="width: 201px; height: 221px;" />
<pre>
<strong>Input:</strong> parent = [-1,0,0,0], s = &quot;aabc&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong> The longest path where each two adjacent nodes have different characters is the path: 2 -&gt; 0 -&gt; 3. The length of this path is 3, so 3 is returned.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == parent.length == s.length</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= parent[i] &lt;= n - 1</code> for all <code>i &gt;= 1</code></li>
	<li><code>parent[0] == -1</code></li>
	<li><code>parent</code> represents a valid tree.</li>
	<li><code>s</code> consists of only lowercase English letters.</li>
</ul>

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        ans = 1

        # we use a table to store the mapping:
        table = {}
        ans_table = {}
        tree_relations = {}
        ans = 1
        for index, node in enumerate(parent):
            # if index not in tree_relations: # e.x. append 0 to keys
            #     tree_relations[index] = []
            
            # if node in tree_relations:
            if node in tree_relations:
                tree_relations[node].append(index)
            else:
                tree_relations[node] = [index]

        for index in range(len(parent)):
            if index not in tree_relations:
                table[index] = 1
                ans_table[index] = 1

        # the following function takes the node (value, index), and previous char
        # output the max length
        def rec_search(
            current_index: int,
            previous_char: str, 
        ) -> int:
            if current_index >= len(parent):
                raise ValueError("Something is wrong with the index")

            if current_index in table:
                return table[current_index]
            
            current_char = s[current_index]
            next_node = current_index

            # get the index for all the available next_node
            next_node_indices = tree_relations[current_index]
            next_node_chars = [s[i] for i in next_node_indices]

            # sweep over the indices
            next_node_max_lengths = []
            for next_node_index, next_node_char in zip(next_node_indices, next_node_chars):
                next_node_max_lengths.append(
                    rec_search(next_node_index, next_node_char)
                )

            cur_max_length = 1
            can_connect_best_length = 0
            can_connect_second_best_length = 0
            for i in range(len(next_node_max_lengths)):
                sub_max_length = next_node_max_lengths[i]
                if next_node_chars[i] != current_char:
                    single_direction_sub_max_length = sub_max_length + 1
                else:
                    single_direction_sub_max_length = 1 # if the sub tree cannot be connected, then the 
                                                        # max length starting from current node is just 1
                cur_max_length = max(cur_max_length, single_direction_sub_max_length)

                # aggregate the results
                if next_node_chars[i] != current_char:
                    if sub_max_length >= can_connect_best_length >= can_connect_second_best_length:
                        can_connect_second_best_length = can_connect_best_length
                        can_connect_best_length = sub_max_length
                    elif can_connect_best_length >= sub_max_length >= can_connect_second_best_length:
                        can_connect_second_best_length = sub_max_length
                    else:
                        pass # do nothing if the length is not good enough

            # aggregate the results for current node (for answer)
            abs_ans = 1 + can_connect_best_length + can_connect_second_best_length
            table[current_index] = cur_max_length
            ans_table[current_index] = abs_ans

            return cur_max_length

        max_length_from_node = rec_search(0, "PLACEHOLDER")


        return max(ans_table.values())
1770