<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>

from copy import copy
class TreeNode:
    def __init__(self, val, c, children=None):
        self.val = val
        self.c = c
        self.children = [] if children is None else children

    def __repr__(self):
        return '[' + str(self.val) + ' | ' + str(self.c) + ' | ' + str([child.val for child in self.children])  + ']'

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        # parent[i] = val
        nodes = {}
        nodes[-1] = TreeNode(-1, '.')

        for i in range(len(parent)):
            if parent[i] in nodes:
                node = nodes[parent[i]]
                if i not in nodes:
                    nodes[i] = TreeNode(i, s[i])
                child = nodes[i]
                node.children.append(child)
            else:
                node = TreeNode(parent[i], s[parent[i]])
                nodes[parent[i]] = node
                if i not in nodes:
                    nodes[i] = TreeNode(i, s[i])
                child = nodes[i]
                node.children.append(child)


        # now we just traverse the tree.
        #print(nodes)
        transit_max = [0]
        start_max = [0]
        longest_path(nodes[-1].children[0], transit_max, start_max)
        return max(start_max[0], transit_max[0])

def longest_path(node, transit_max, start_max):
    """
    returns:
      - longest path assuming you start from node
    """
    if node is None:
        return 0
    
    if len(node.children) == 0:
        transit_max[0] = max(transit_max[0], 1)
        start_max[0] = max(start_max[0], 1)
        return 1

    stc = {}
    for child in node.children:
        stc[child] = longest_path(child, transit_max, start_max)

    # calculate longest path assuming you start from node
    longest_path_start = 1
    add = 0
    for i, child in enumerate(node.children):
        if child is not None and child.c != node.c:
            add = max(add, stc[child])
    longest_path_start += add
    start_max[0] = max(start_max[0], longest_path_start)

    # calculate longest path assuming transit
    transit_path_len = 1
    lens = []
    for i, child in enumerate(node.children):
        if child is not None and child.c != node.c:
            lens.append(stc[child])
    lens = sorted(lens)
    if len(lens) >= 1:
        transit_path_len += lens[-1]
    if len(lens) >= 2:
        transit_path_len += lens[-2]

    transit_max[0] = max(transit_max[0], transit_path_len)

    """
    # calculate longest path among children
    len_path_among_children = 0
    for i, child in enumerate(node.children):
        len_path_among_children = max(len_path_among_children, max(stc[child]))"""

    return longest_path_start




1831