<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>

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int dp[100100][2]; // 0 0 -> root is a and and it is ending at root 0 1 -> root is a and root is middle

void dfs(int node, int par, string &S, vector<vector<int>> &g){
    char need;
    if(S[node] == 'a') need = 'b';
    else need = 'a';
    priority_queue<int> pqend;
    priority_queue<int> pqmid;
    for(auto child: g[node]){
        if(child != par){
            dfs(child, node, S, g);
            if(S[child]!=S[node]) {
                pqend.push(dp[child][0]);
                pqmid.push(dp[child][1]);
            }
        }
    }
    int firstmax = 0, secondmax = 0;
    if(!pqend.empty()) {
        firstmax = pqend.top();
        pqend.pop();
    }
    if(!pqend.empty()) {
        secondmax = pqend.top();
        pqend.pop();
    }
    // int midmax = 0;
    // if(!pqmid.empty()){
    //     midmax = pqmid.top();
    //     pqmid.pop();
    // }
    dp[node][0] = 1 + firstmax;
    dp[node][1] = 1 + firstmax + secondmax;
    // cout<<node<<" - "<<firstmax<<" & "<<secondmax<<endl;

}



class Solution {
public:
    int longestPath(vector<int>& A, string &S) {
        // Implement your solution here
    int n = A.size();
    vector<vector<int>> g(n);
    for(int i = 1; i<n; i++){
        g[i].push_back(A[i]);
        g[A[i]].push_back(i);
    }
    for(int i = 0 ;i<n; i++){
        dp[i][0] = 0;
        dp[i][1] = 0;
        dp[i][0] = 0;
        dp[i][1] = 0;
    }
    dfs(0, -1, S, g);
    int ans = 0;
    for(int i = 0; i<n; i++){
        ans = max(ans, dp[i][1]);
        ans = max(ans, dp[i][1]);
        ans = max(ans, dp[i][0]);
        ans = max(ans, dp[i][0]);
    }
    return ans;

    }
};
274774