<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 typing import List

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        """
        Computes the length of the longest path in a tree where no two adjacent nodes
        have the same character.

        The tree is represented by the `parent` array, where `parent[i]` is the parent of the `i-th` node.
        The characters of the nodes are given by the string `s`.

        Time Complexity: O(n) - Each node is visited exactly once during the DFS traversal.
        
        Space Complexity: O(n) - Space is used for storing the children list and the recursion stack.

        Parameters:
        parent (List[int]): An array representing the tree, where `parent[i]` is the parent of the `i-th` node.
        s (str): A string where each character represents the value of the corresponding node in the tree.

        Returns:
        int: The length of the longest path with different adjacent characters.
        """
        
        # Create a list of lists to store the children of each node
        children = [[] for _ in range(len(parent))]
        
        # Build the tree by associating each node with its children
        for child_node in range(1, len(parent)):
            parent_node = parent[child_node]
            children[parent_node].append(child_node)
        
        # Initialize the maximum path length
        max_path_length = 0

        def dfs(node: int) -> int:
            """
            Performs a Depth-First Search (DFS) to calculate the longest path
            starting from the current node where adjacent characters are different.
            
            Parameters:
            node (int): The node to start the DFS from.
            children (List[List[int]]): A list of lists where each index represents a node and contains its children.
            s (str): A string where each character represents the value of each node.

            Returns:
            int: The length of the longest path that ends at the current node.
            """
            
            nonlocal max_path_length  # Access the max_path_length variable defined in the enclosing function
            
            # Initialize variables to keep track of the longest and second longest chains
            longest_chain = 0
            second_longest_chain = 0
            
            # Explore all children of the current node
            for child in children[node]:
                # Recursively find the longest path starting from this child
                current_chain_length = dfs(child)
                
                # Only consider this path if the characters of the parent and child nodes are different
                if s[node] != s[child]:
                    # Update the longest and second longest chains if necessary
                    if current_chain_length > longest_chain:
                        # Update both longest and second longest chains
                        second_longest_chain = longest_chain
                        longest_chain = current_chain_length
                    elif current_chain_length > second_longest_chain:
                        # Update only the second longest chain
                        second_longest_chain = current_chain_length
            
            # Update the global maximum path length
            max_path_length = max(max_path_length, longest_chain + second_longest_chain + 1)
            
            # Return the length of the longest chain that ends at this node, including the node itself
            return longest_chain + 1

        # Start DFS from the root node (0)
        dfs(0)
        
        # Return the maximum path length found
        return max_path_length

1043