<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 {
public:
    string chars;
//     int getMaxLengthPath(int &maxPath, vector<vector<int>> &tree,int node){
//         cout<<"Node "<<node<<endl;
//         if(tree[node].size()==0){
//             cout<<"no child"<<endl;
//             maxPath=max(maxPath,1);
//             return 1;
//         }
//         // int childrenCount=tree[node].size();
//         vector<int> childrenPathLengths;
//         for(auto x: tree[node]){
//             if(chars[node]!=chars[x]){
//                 childrenPathLengths.push_back(1+getMaxLengthPath(maxPath,tree,x));
//             }
//         }
//         int sz=childrenPathLengths.size();
//         if(sz==0)
//             return 1;
        
//         sort(childrenPathLengths.begin(),childrenPathLengths.end());
//         maxPath=max(maxPath,childrenPathLengths[sz-1]+(sz>1?childrenPathLengths[sz-2]-1:0));
//         cout<<"child array after sorting ";
//         for(auto x: childrenPathLengths)
//             cout<<x<<" ";
        
//         cout<<endl;
//         return childrenPathLengths[sz-1];
//     }
    int dfs(int node, vector<vector<int>> &tree,vector<bool> &vis, int &ans){
        vis[node]=true;
        if(tree[node].size()==0)
        {
            ans=max(ans,1);
            return 1;
        }
        vector<int> childrenPathLengths;
        for(auto x: tree[node]){
            childrenPathLengths.push_back(1+dfs(x,tree,vis,ans));
        }
        int sz=childrenPathLengths.size();
        sort(childrenPathLengths.begin(),childrenPathLengths.end());
        if(sz==1)
            ans=max(ans,childrenPathLengths[sz-1]);
        if(sz>=2){
            ans=max(ans,childrenPathLengths[sz-1]+childrenPathLengths[sz-2]-1);
        }
        return childrenPathLengths[sz-1];
    }
    int longestPath(vector<int>& parent, string s) {
        int nodeCount=s.size();
        chars=s;
        vector<vector<int>> tree(nodeCount);
        for(int itr=1;itr<parent.size();itr++){
            if(s[parent[itr]]!=s[itr])
                tree[parent[itr]].push_back(itr);
        }
        int maxPath=0;
        vector<bool> vis(nodeCount, false);
        for(int i=0;i<nodeCount;i++){
            if(!vis[i]){
                int ans=0;
                dfs(i,tree,vis,ans);
                maxPath=max(maxPath,ans);
            }
        }
   
        
        return maxPath;
    }
};
238034