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

import heapq as heap 

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        '''
        use DP
        let a[i] be the max len path starting from i
        let b[i] be the max len path in the subtree rooted at i
        for children c1, c2 of i
        a[i] = max(1, 
                   (if c1 != None, s[i] != s[c1]) a[c1] + 1, 
                   (if c2 != None, s[i] != s[c2]) a[c2] + 1
                   )
        b[i] = max(b[c1], b[c2], a[i])
        return b[0]
        '''
        
        #print(f'parent = {parent}')
        
        n = len(parent)
        children = [[] for _ in range(n)]
        
        for (i, p) in enumerate(parent):
            # parent of node i is p
            if i > 0:
                children[p].append(i)
        
        #print(f'children = {children}')
        
        max_from_node = [None for _ in range(n)]
        max_in_subtree = [None for _ in range(n)]
        
        def helper(root):
            #print(f'At node {root}')
            if max_from_node[root] is not None:
                return
            c = children[root]
            if len(c) == 0:
                # this is leaf
                #print(f'This is leaf, returning')
                max_in_subtree[root] = 1
                max_from_node[root] = 1
                #print(f'max in subtree = {max_in_subtree}, max from node = {max_from_node}')
                return
            maxfromnode = 1
            maxsubtree = 1
            #print(f'Not a leaf, visiting childrens {[c]}')
            max2 = []
            for node in c:
                helper(node)
                maxfromnode = max(maxfromnode, (s[root] != s[node]) * (1 + max_from_node[node]))
                maxsubtree = max(maxsubtree, max_in_subtree[node])
                temp = (s[root] != s[node]) * max_from_node[node]
                if len(max2) < 2:
                    max2.append(temp)
                elif temp > min(max2):
                    temp = sorted(max2 + [temp])
                    max2 = temp[-2:]
                #print(f'at node {root}, max2 = {max2}') 
            maxsubtree = max(sum(max2) + 1, maxsubtree)
                
                
            '''
            print(f'back to node {root}'):
            if s[root] != s[node]:
                maxfromnode = max(maxfromnode, max_from_node[node] + 1)
            maxsubtree = max(maxfromnode, max_in_subtree[node])
            print(f'updated maxfromnode = {maxfromnode}, maxsubtree = {maxsubtree}')'''
            max_from_node[root] = maxfromnode
            max_in_subtree[root] = maxsubtree
            #print(f'returning from node {root}')
            #print(f'max from node = {max_from_node}')
            #print(f'max in subtree = {max_in_subtree}')
        
        helper(0)
        return max_in_subtree[0]
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
        
        
1443