<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 Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        graph = collections.defaultdict(list)
        for i, v in enumerate(parent):
            if i == 0:
                continue
            graph[i].append(v)
            graph[v].append(i)
        
        def f(u):
            best, second_best = 0, 0
            for v in graph[u]:
                if v in seen:
                    continue
                
                seen.add(v)
                v_best = f(v)

                if s[v] == s[u]:
                    continue

                if v_best >= best:
                    best, second_best = v_best, best
                elif v_best > second_best:
                    second_best = v_best
            
            res[0] = max(res[0], best + second_best + 1)
            return best + 1
        
        res = [1]
        seen = set([0])
        f(0)
        return res[0]































        
        
        
    #     # solution redone here
    #     # original solution further below
    #     graph = collections.defaultdict(list)
    #     n = len(parent)
    #     for i in range(1, n):
    #         p = parent[i]
    #         graph[p].append(i)
    #         graph[i].append(p)
        
    #     best = [1]
    #     def dp(curr, seen):
    #         # find the two best neighbors of curr
    #         heap_arr = [0, 0]
    #         c = s[curr]
    #         for neighbor in graph[curr]:
    #             if neighbor in seen:
    #                 continue
    #             # maybe the best path does not include the root
    #             seen.add(neighbor)
    #             neighbor_amt = dp(neighbor, seen)
    #             if c != s[neighbor]:
    #                 heapq.heappush(heap_arr, neighbor_amt)
    #                 if len(heap_arr) > 2:
    #                     heapq.heappop(heap_arr)
    #         one_child_path_length = 1 + heap_arr[1]
    #         two_child_path_length = 1 + sum(heap_arr)
    #         best[0] = max(best[0], one_child_path_length, two_child_path_length)
    #         return one_child_path_length
        
    #     dp(0, set([0]))
    #     return best[0]





































































    #     if len(parent) == 1:
    #         return 1
    #     adjacency = {}
    #     for v in range(1, len(parent)):
    #         p = parent[v]
    #         if v in adjacency:
    #             adjacency[v].append(p)
    #         else:
    #             adjacency[v] = [p]
    #         if p in adjacency:
    #             adjacency[p].append(v)
    #         else:
    #             adjacency[p] = [v]
        
    #     seen = set()
    #     seen.add(0)
    #     _, res = self.dfs(0, adjacency, seen, s)
    #     return res

    # def dfs(self, curr, adjacency, seen, s):
    #     # returns longest path that starts at curr, and res, which is longest of all
    #     # paths that are in the subtree of curr
    #     heap_arr = [0, 0]
    #     res = 0
    #     for neighbor in adjacency[curr]:
    #         if neighbor not in seen:
    #             seen.add(neighbor)
    #             neighbor_length, res_neighbor = self.dfs(neighbor, adjacency, seen, s)
    #             res = max(res, res_neighbor)
    #             if s[neighbor] != s[curr]:
    #                 smallest = heapq.heappop(heap_arr)
    #                 heapq.heappush(heap_arr, max(smallest, neighbor_length))
    #     # this is the length of the longest path that goes through one child
    #     one_child_path_length = 1 + heap_arr[1]
    #     # this is the length of the longest path that goes through two children
    #     two_child_path_length = 1 + heap_arr[0] + heap_arr[1]
    #     res = max(res, two_child_path_length)
    #     res = max(res, one_child_path_length)
    #     return one_child_path_length, res
1370