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

"""
___
Goal
___

return longset path length 

___
Examples:
___

Input: parent = [-1,0,0,1,1,2], s = "abacbe"
Output: 3




___
Assumptions
___

1. we are returning length of longest path

2. there should be no pair of adjacent nodes on path with the same character 
    ex. 

3. tree is rooted at node 0

4. tree consists of nodes from 0 to n - 1

5. parent[i] is parent of node i

6. s[i] is the character of node i

___
PsuedoCode:
___

Topological Sort:
    - used to efficiently prune the child nodes



"""

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        
        indegree = [0 for _ in parent]
        edges = {}
        child_paths = [[0, 0] for _ in parent]

        for node, ancestor in enumerate(parent):
            if node:
                if node not in edges:
                    edges[node] = []
                edges[node].append(ancestor)
                indegree[ancestor] += 1
        
        queue = deque([n for n, d in enumerate(indegree) if not d])
        max_length = 0
        while queue:

            node = queue.popleft()
            max_length = max(max_length, 1 + sum(child_paths[node]))
            for p in edges.get(node, []):
                indegree[p] -= 1
                heappushpop(child_paths[p], 1 + child_paths[node][1] if s[node] != s[p] else 0)
                if not indegree[p]:
                    queue.append(p)

        return max_length
49125