<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 collections import defaultdict
class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        n = len(parent)

        adjList = defaultdict(list)
        
        for i in range(n):
            if parent[i] != -1:
                adjList[parent[i]].append(i)
        # [print(f"{k}:{v}") for k, v in adjList.items()]
        
        def enumerat(node, prev):
            highest = 0
            highest2 = 0

            for child in adjList[node]:
                res = enumeratHelper(child, s[node])
                if res > highest2 and res > highest:
                    highest2 = highest
                    highest = res
                elif res > highest2:
                    highest2 = res
            
            return (highest, highest2)
                
        def enumeratHelper(node, prev):
            count = 0
            
            if s[node] != prev:
                count = 1
                
                for child in adjList[node]:
                    count = max(count, 1 + enumeratHelper(child, s[node]))
            
            return count
                
        
        def dfs(node):
            # pre-order dfs
            enumerateRes = enumerat(node, None)
            
            highest = sum(enumerateRes) + 1 
            
            if highest == n: return n
            
            for child in adjList[node]:
                highest = max(highest, dfs(child))
            
            return highest
        
        return dfs(0)
            
        
        
            
            
    
        
        
'''
from collections import defaultdict

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        n = len(parent)
        if n == 1:
            return 1
        
        adjList = defaultdict(list)
        for i in range(n):
            if parent[i] != -1:
                adjList[i].append(parent[i])
                adjList[parent[i]].append(i)
        
        def recur(curr, prev, prev2):
            # print('curr', curr, 'prev', prev, 'prev2', prev2, 's[curr]', s[curr])
            maxSize = 0
            
            if prev is None and prev2 is None or (prev2 is None and s[prev] != s[curr]) or \
                (prev is not None and prev2 is not None and curr != prev2 and s[curr] != s[prev]):
                
                # print(f"nbr for {curr}: {adjList[curr]}")
                for nbr in adjList[curr]:
                    maxSize = max(maxSize, 1 + recur(nbr, curr, prev))
                    
            return maxSize
                
        ans = 0    
        for start in range(n):
            # print('start', s[start])
            ans = max(ans, recur(start, None, None))
            
        return ans
    
'''
75575