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

#include <vector>
#include <string>
#include <functional> // Include for std::function

class Solution {
public:
    // Function to find the longest path where each character is different 
    // from its parent in a tree defined by parent-child relationships and node values given by string s.
    int longestPath(vector<int>& parent, string& s) {
        int numNodes = parent.size(); // Total number of nodes in the tree.
        vector<vector<int>> graph(numNodes);
      
        // Build the adjacency list representation of the tree from the parent array.
        for (int i = 1; i < numNodes; ++i) {
            graph[parent[i]].push_back(i);
        }
      
        // Variable to store the length of the longest path found.
        int longestPathLength = 0;
      
        // Define the depth-first search (DFS) function using lambda notation.
        std::function<int(int)> dfs = [&](int currentNode) -> int {
            // The maximum path length through this node.
            int maxLengthThroughCurrent = 0;
          
            // Explore all child nodes of the current node.
            for (int child : graph[currentNode]) {
                // Recursively perform DFS from the child node.
                int pathLengthFromChild = dfs(child) + 1; // +1 for the edge from the current node to the child node.
              
                // If the current node and the child have different characters,
                // try to extend the path.
                if (s[currentNode] != s[child]) {
                    // Update the longest path if combining two paths through this node
                    // results in a longer path.
                    longestPathLength = max(longestPathLength, maxLengthThroughCurrent + pathLengthFromChild);
                  
                    // Update the maximum length of the path that goes through the current node.
                    maxLengthThroughCurrent = max(maxLengthThroughCurrent, pathLengthFromChild);
                }
            }
          
            // Return the max length of the path through the current node to its parent.
            return maxLengthThroughCurrent;
        };
      
        // Start DFS from the root node (0).
        dfs(0);
      
        // Return the length of the longest path. We add 1 because the path length
        // is the number of nodes on the path, but longestPathLength stores the number of edges.
        return longestPathLength + 1;
    }
};
176035