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

"""
思路：这题是一道常规的 DFS tree traversal 计算 longtest path 的题，tricky part：
1. 没有直接给 tree node，我们需要根据 parent 构建 adjacent list (每个 node 的 children 都有哪些，Adjacent list 不指向 parent)
2. 当 parent 和 child 的字母一样时，不考虑 child return 回来的 length

Edge case:
  1. 当发现 current node 和 child 的字母一致时，不能直接 skip 那个 child，因为 final path 可能还在那个 child 的 subtree 中。所以，我们只是 discard child return 回来的 path length，但还是要 traverse child. 
  sample inut: parent = [-1, 0, 1], s = "aab"， i.e. node 0 和 node 1 都是 “a”
    for child in adjacentList[curNode]:    
        childPath = self.__traverseTree(adjacentList, child, maxLength, s)
        if s[curNode] == s[child]:
            # discard childPath
            continue
"""
from collections import defaultdict
class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        # edge case
        if not parent:
            return 0
        elif len(parent) == 1:
            return 1

        adjacentList = self.__buildAdjacentList(parent)
        maxLength = [0]

        self.__traverseTree(adjacentList, 0, maxLength, s)

        return maxLength[0]
    
    def __buildAdjacentList(self, parent: List[int]) -> Dict[int, List[int]]:
        adjacentList = defaultdict(list)
        
        for index, nodeParent in enumerate(parent):
            if nodeParent == -1:
                continue
            
            adjacentList[nodeParent].append(index)
        
        return adjacentList
    
    def __traverseTree(self, adjacentList: Dict[int, List[int]], curNode: int, maxLength: List[0], s: str) -> int:
        # base case
        if curNode not in adjacentList:
            # current node is a leaf
            return 1
        
        longestPath = 0
        secondLongestPath = 0

        for child in adjacentList[curNode]:    
            childPath = self.__traverseTree(adjacentList, child, maxLength, s)

            if s[curNode] == s[child]:
                # discard childPath
                continue

            if childPath > longestPath:
                secondLongestPath = longestPath
                longestPath = childPath
            elif childPath > secondLongestPath:
                secondLongestPath = childPath
            
        maxLength[0] = max(maxLength[0], longestPath + secondLongestPath + 1)

        return 1 + (longestPath if longestPath > 0 else secondLongestPath)
1006