<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 longestPath(vector<int>& parents, string s) {
        int n = parents.size();
        // Store the number of children for each node
        vector<int> graph(n, 0); 

        // Count the number of children for each node
        for (int i = 1; i < n; i++) 
            graph[parents[i]]++;

        queue<int> queue;
        // Add all leaf nodes to the queue (nodes with no children)
        for (int i = 0; i < n; i++) {
            if (graph[i] == 0) {
                queue.push(i);
            }
        }

        // This will store the longest valid path
        int maxLength = 1; 
        // Keeps track of the longest path for each node
        
        const int range = static_cast<int>(1e5);
        int length[range + 1] {[0 ... range] = 1}; 
        // int length[100005] = { [0 ... 100004] = 1 }; 

        // Process nodes in topological order
        while (!queue.empty()) {
            int node = queue.front(); 
            queue.pop();

            // Skip the root node
            if (node == 0) 
                continue;
            
            // Get the parent of the current node
            int parent = parents[node]; 

            // If the character at this node is different from its parent
            if (s[node] != s[parent]) {
                // Update the longest path if this path is better
                maxLength = max(maxLength, length[node] + length[parent]);
                // Update the parent's subtree size with the best option
                length[parent] = max(length[node] + 1, length[parent]);
            }

            // Decrement the parent's child count, and 
            // if no children remain, add the parent to the queue
            if (--graph[parent] == 0){
                queue.push(parent);
            }
        }

        // Return the longest path found
        return maxLength; 
    }
};

107148