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

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        children = [[] for _ in range(len(parent))]

        for j in range(1, len(parent)):
            children[parent[j]].append(j)

        leaves = set()
        for j in range(len(parent)):
            if not children[j]:
                leaves.add(j)
        
        next_nodes = children[0]
        stack = [0]

        while next_nodes:
            l = len(next_nodes)
            # print(l)
            stack.extend(next_nodes)
            next_nodes = []

            for j in range(len(stack) - 1, len(stack) - 1 - l, - 1):
                next_nodes.extend(children[stack[j]])
        
        max_length = 1
        branches = [[0, 0] for _ in range(len(parent))]
        while stack:
            curr = stack.pop()
            if curr in leaves:
                continue
            
            longest_branches = [0, 0]
            for c in children[curr]:
                if s[curr] == s[c]:
                    continue
                branch = branches[c][0] + 1
                if branch >= longest_branches[0]:
                    longest_branches[1] = longest_branches[0]
                    longest_branches[0] = branch
                else:
                    if branch > longest_branches[1]:
                        longest_branches[1] = branch

            branches[curr] = longest_branches
            max_length = max(max_length, sum(longest_branches) + 1)

        return max_length

        # def find_branches(n):
        #     if n in leaves:
        #         return [0, 0]

        #     longest_branches = [0, 0]
        #     for c in children[n]:
        #         branch = find_branches(c)[0] + 1

        #         if s[n] == s[c]:
        #             continue

        #         if branch >= longest_branches[0]:
        #             longest_branches[1] = longest_branches[0]
        #             longest_branches[0] = branch
        #         else:
        #             if branch > longest_branches[1]:
        #                 longest_branches[1] = branch
            
        #     max_length[0] = max(max_length[0], sum(longest_branches) + 1)

        #     return longest_branches

        # max_length = [1]

        # children = [[] for _ in range(len(parent))]

        # for j in range(1, len(parent)):
        #     children[parent[j]].append(j)

        # leaves = set()
        # for j in range(len(parent)):
        #     if not children[j]:
        #         leaves.add(j)
        
        # find_branches(0)

        # return max_length[0]
1346