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

"""
longest alternating path in a tree r with child subtrees c1, ..., cn
denote this as L[r]

longest alternating path in a tree r ending at r denote as P[r]

P[r] = max(
    1,  (the path containing just r)
    P[c1]+1 if c1 != r, ..., P[cn]+1 if cn != r,  (the path is one longer than a path ending at a child)
)
L[r] = max(
    1,  (the path containing just r)
    L[c1], ..., L[cn],  (the path is entirely within a subtree)
    P[r],
    P[ci]+1+P[cj] if ci != r and r != cj, (the path connects two longest child paths)
)
"""

from collections import deque
from heapq import nlargest

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        # assume (pray) that values in parent are non-decreasing
        n = len(s)

        children = [[] for _ in range(n)]
        for i, p in enumerate(parent):
            if p != -1:
                children[p].append(i)

        def search(r: int) -> tuple[int, int]:  # L[r], P[r]
            if len(children[r]) == 0:
                return 1, 1
            best_p = 0
            next_best_p = 0
            best_l = 0
            for child in children[r]:
                l, p = search(child)
                if l > best_l:
                    best_l = l
                if s[r] != s[child]:
                    if p > best_p:
                        next_best_p = best_p
                        best_p = p
                    elif p > next_best_p:
                        next_best_p = p
            p = max(1, best_p+1)
            return max(1, best_l, p, best_p+1+next_best_p), p


        return search(0)[0]

        # level_order = []
        # q = deque()
        # q.append(0)
        # while len(q) > 0:
        #     cur = q.popleft()
        #     level_order.append(cur)
        #     q.extend(children[cur])

        # longest_ending_at = [1 for _ in range(n)]  # P[r]
        # longest_in = [1 for _ in range(n)]  # L[r]

        # for i in reversed(level_order):
        #     l = nlargest(2, (longest_ending_at[j] for j in children[i] if s[j] != s[i]))

        #     while len(l) < 2:
        #         l.append(0)

        #     longest_ending_at[i] = max(1, l[0]+1)

        #     ugh = max((longest_in[j] for j in children[i]), default=0)

        #     longest_in[i] = max(1, ugh, longest_ending_at[i], l[0]+1+l[1])

        # return longest_in[0]

62925