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

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        graph = defaultdict(list)
        
        # Build the tree structure
        for i, p in enumerate(parent):
            graph[p].append(i)
        
        ans = 1

        def dfs(node: int) -> int:
            nonlocal ans  # Declare that we are using the 'ans' variable from the outer scope
            longest = second_longest = 0
            
            for child in graph[node]:
                path_length = dfs(child)
                
                if s[child] != s[node]:
                    if path_length > longest:
                        second_longest = longest
                        longest = path_length
                    elif path_length > second_longest:
                        second_longest = path_length
            
            ans = max(ans, longest + second_longest + 1)
            return longest + 1
        
        dfs(0)
        return ans

class Solution:
    def longestPath(self, parent, s):
        child_graph = defaultdict(list)
        
        for i, p in enumerate(parent):
            child_graph[p].append(i)
        
        res = 1

        def search_child(node):
            nonlocal res

            longest = second_longest = 0

            if not child_graph[node]:
                return longest + 1
            
            for child in child_graph[node]:
                path_length = search_child(child)

                if s[child] != s[node]:
                    if path_length > longest:
                        longest, second_longest = path_length, longest
                    elif path_length > second_longest:
                        second_longest = path_length

            res = max(res, longest + second_longest + 1)
            return longest + 1

        search_child(0)
        return res

class Solution:
    def __init__(self):
        self.res = 1
    def longestPath(self, parent, s):
        children = defaultdict(list)
        for i, p in enumerate(parent):
            children[p].append(i)

        def deeper_length(node):
            if not children[node]:
                return 1

            longest = second_longest = 0
            for child in children[node]:
                child_path = deeper_length(child)

                if s[child] != s[node]:
                    if child_path > longest:
                        longest, second_longest = child_path, longest
                    elif child_path > second_longest:
                        second_longest = child_path
            self.res = max(self.res, longest + second_longest + 1)
            return longest + 1

        deeper_length(0)
        return self.res

class Solution:
    def __init__(self):
        self.max_length = 1

    def longestPath(self, parent,s):
        if not parent:
            return 0
        children = defaultdict(list)
        for i, p in enumerate(parent):
            children[p].append(i)
        def dfs(node):
            #base case
            longest = second_longest = 0
            if not children[node]:
                return 1
#1 parent nodes representing child tree
#2 string characters assigned to each child tree node matching tree structured index
#3 return longest path such that no pair of adj nodes on the path duplicate
            for child in children[node]:
                curr_child_length = dfs(child)
                if s[child] != s[node]:
                    if curr_child_length > longest:
                        longest, second_longest = curr_child_length, longest
                    elif curr_child_length > second_longest:
                        second_longest = curr_child_length

            self.max_length = max(self.max_length, longest + second_longest + 1)
            return longest + 1 

        dfs(0)
        return self.max_length
            





        """
        dfs()

    -1(a) 
  0(b)    0(a)
1(c) 1(b)    2(e)

    0(a) 
  1(b)    2(a)
3(c) 4(b)    5(e)
"""








1055