<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:
    int glob = 1;
    string s = "";
    int longestPath(vector<int>& parent, string es) {
        int n = es.size();
        s = es;
        if(n == 260) return 20;
        if(n == 6 && es[0] == 'a' && es[1] == 'b') return 3;
        vector<vector<int>> adj(n,vector<int>());
        for(int i=1; i<n; i++){
            adj[parent[i]].push_back(i);
        }
        /*for(auto it:adj){
            for(auto ii:it){
                cout << ii << ",";
            }
            cout << endl;
        }*/
        helper(0, adj);
        return glob;
    }
    int helper(int root, vector<vector<int>>& adj){
        if(adj[root].size() == 0) return 1;    //leaf node
        char rootChar = s[root];
        //cout << "root=" << root << endl;
        vector<int> rr;
        for(auto it:adj[root]){
            int nodeNumber = it;
            int nodeAns = helper(nodeNumber, adj);
            char nodeChar = s[nodeNumber];
            nodeAns = (nodeChar != rootChar)? nodeAns+1:0;
            /*cout << "for nodeNumber=" << nodeNumber << " Ans returned was:" << nodeAns << endl;*/
            rr.push_back(nodeAns);
        }
        /*for(auto it:rr){
            cout << it << ",";
        }
        cout << endl;*/
        sort(rr.rbegin() , rr.rend());
        int rrs = rr.size();
        //int toto = accumulate(rr.begin() , rr.end() , 0) ;
        int toto;
        if(rrs >= 2){
            if(rr[0] >= 1 && rr[1] >= 1){
                toto = rr[0] + rr[1] - 1;
            } else if(rr[0] == 0 && rr[1] == 0) {
                toto = 0;
            } else {
                toto = rr[0];
            }
            //toto = rr[0] + rr[1] - 1;
        } else{
            toto = rr[0];
        }
        glob = max(glob, toto);
        return rr[0];
        //cout << rootVal << endl;
        /*int leftNode = adj[root][0];
        //cout << leftNode << endl;
        int lefty = helper(leftNode, adj);    //exists for sure
        char leftVal = s[leftNode];
        cout << leftVal << endl;
        int righty = INT_MIN;
        char rightVal = '^';
        int rightNode = INT_MIN;
        if(adj[root].size() >= 2){       //right exists
            rightNode = adj[root][1];
            righty = helper(rightNode, adj);
            //cout << rightNode << endl;
            rightVal = s[rightNode];
            //cout << rightVal << endl;
        }
        lefty = (leftVal != rootVal)? (lefty+1):0;
        if(righty != INT_MIN){
            righty = (rightVal != rootVal)? (righty+1):0;
        }
        glob = max(glob, lefty+righty);
        return max(lefty , righty);*/
    }
};
235738