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

class Node:
    def __init__(self, val=0):
        self.val = val
        self.child = []

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        def recurse(nodes, s, node):
            # many different type of paths
            # (1) longest path exists below current node
            # (2) longest path exists below current node, plus node
            # (3) longest path exists by connecting left and right children of current node
            # ----
            # recurse return (int, int): longest path below node (not including), longest including node

            # leaf
            if len(node.child) == 0:
                return 1, 1
            
            non_bridges, bridges = [], []
            for child in node.child:
                c, cb = recurse(nodes, s, nodes[child])
                if s[node.val] != s[child]:
                    bridges.append(cb + 1)
                    non_bridges.append(cb + 1)
                non_bridges.append(c)
            # more than one child have different char to node
            if len(bridges) > 1:
                bridges.sort(reverse=True)
                non_bridges.append(bridges[0] + bridges[1] - 1)
            
            # (longest path at node, longest path to node)
            #print(node.val, non_bridges, bridges)
            mb = max(bridges) if len(bridges) > 0 else 1
            return max(non_bridges), mb
            
        n = len(s)
        nodes = {}
        root = None
        for val in range(0, n):
            if val not in nodes:
                node = Node(val)
                nodes[val] = node
            if parent[val] == -1:
                root = nodes[val]
                continue

            if parent[val] not in nodes:
                p = Node(parent[val])
                nodes[parent[val]] = p
            p = nodes[parent[val]]
            p.child.append(val)
        
        c, cb = recurse(nodes, s, root)
        return max(c, cb)
1467