<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 Node:
    def __init__(self, val):
        self.val = val
        self.children = []

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        # dynamic programming question
        # 4 states, either we came from nothing (start at this node), came from parent (1), came from left (2), came from right (3)
        nodes_dict = dict()

        nodes_dict = {}
        for i in range(len(parent)):
            if i not in nodes_dict:
                nodes_dict[i] = Node(s[i])
            if parent[i] != -1:  # Ensure this is not the root node
                if parent[i] not in nodes_dict:
                    nodes_dict[parent[i]] = Node(s[parent[i]])
                nodes_dict[parent[i]].children.append(nodes_dict[i])

        root = nodes_dict[0]
        # def dp(curr, direction):
        #     if (curr, direction) in memo:
        #         return memo[(curr,direction)]
            
        #     curr_max = 0
        #     possible = [("1", curr.parent), ("2", curr.left), ("3", curr.right)]

        #     if direction == "1":
        #         possible.pop(0)
        #     elif direction == "2":
        #         possible.pop(1)
        #     elif direction == "3":
        #         possible.pop(2)
            
        #     for num, node in possible:
        #         if node and curr.val != node.val:
        #             if num == "1":
        #                 if curr.parent.left == curr:
        #                     curr_max = max(curr_max, dp(curr.parent, "2") + 1)
        #                 else:
        #                     curr_max = max(curr_max, dp(curr.parent, "3") + 1)
        #             elif num == "2":
        #                 curr_max = max(curr_max, dp(curr.left, "1") + 1)
        #             else:
        #                 curr_max = max(curr_max, dp(curr.right, "1") + 1)
            
        #     memo[(curr,direction)] = curr_max
        #     return curr_max
        
        # global_max = 0
        # def traverseTree(curr):
        #     nonlocal global_max

        #     if not curr:
        #         return
            
        #     if curr.val == "b":
        #         print(1 + dp(curr, None))
        #     global_max = max(global_max, 1 + dp(curr, None))
        #     traverseTree(curr.left)
        #     traverseTree(curr.right)

        # traverseTree(root)

        # return global_max

        # for our dfs function, we will return the maximum of the left and right distances
        # we will have a global maximum for the longest left path + 1 + longest right path
        global_max = 0

        def dfs(curr):
            nonlocal global_max
            one = 0
            two = 0
            if not curr:
                return 0

            for node in curr.children:
                res = dfs(node)
                if curr.val != node.val:
                    if res > one:
                        one, two = res, one
                    elif res > two:
                        two = res
            
            global_max = max(global_max, 1 + one + two)

            return one + 1
        
        dfs(root)

        return global_max
1479