<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:
        t={}
        for i in range(1,len(parent)):
            if parent[i] not in t:
                t[parent[i]]=[i]
            else:
                t[parent[i]].append(i)
        
        self.ans=1
        def fun(i):
            if i not in t:
                return 1
            res = 1
            for j in t[i]:
                length=fun(j)
                if s[i] != s[j]:
                    self.ans = max(self.ans,length+res)
                    res = max(res,length+1)
            return res
        
        fun(0)
        return self.ans

        '''
        max_len = 0 
        #max_par = max(parent)
        #ind = [i for i in range(len(parent))]
        if len(set(s)) == 1:
            return 1

        def find_max(p_node):
            nonlocal max_len
            
            if p_node not in parent: # is leaf node
                return 1, s[p_node] #only length 1

            to_ret_len = 0
            sec_len = 0
            valid_c_len = []
            for i in range(p_node+1, len(parent)):
                if parent[i] == p_node:
                    len_p, s_p = find_max(i)

                    if s[p_node] != s_p:
                        valid_c_len.append(len_p)
                        if len_p > to_ret_len:
                            to_ret_len = len_p
                        elif len_p <= to_ret_len and len_p > sec_len:
                            sec_len = len_p
 
            new_len = 1 + to_ret_len + sec_len
            max_len = max(max_len, new_len)
            return 1+to_ret_len, s[p_node]

        root_len, root_s = find_max(0)
        max_len = max(max_len, root_len)
        return max_len
        '''
66375