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

/*
    Do this recursively. For each node, let's figure out 
    (A) the longest path UP into it 
    (B) the longest path DOWN into it

    Longest path up is simple DFS.

    Two choices for the longest path down -> we can choose one of the 
    UP paths into the parent (other than our up path) and add 1 to it,
    or we can take 1 plus the longest DOWN path into the parent.

    UP path is 0 if the parent has the same character as us, otherwise computed
    as above.

    DOWN path is the max of the children that have different characters from us.
*/
class Solution {
private:
    using node_t = int;
    static constexpr node_t ROOT_NODE = 0;
    vector<int> upPaths;
    vector<int> downPaths;

    void fillUpPaths(const vector<node_t>& parent, const vector<vector<node_t>>& children, 
                    const string& s, int node = ROOT_NODE)
    {
        int longestUpPath = 1;
        char myChar = s[node];
        for(node_t child : children[node])
        {
            fillUpPaths(parent, children, s, child);

            if(s[child] != myChar)
            {
                longestUpPath = max(longestUpPath, 1 + upPaths[child]);
            }
        }
        upPaths[node] = longestUpPath;
    }
    void fillDownPaths(const vector<node_t>& parent, const vector<vector<node_t>>& children,
                    const string& s, node_t node = ROOT_NODE)
    {
        /* Compute my longest down path */
        downPaths[node] = [&]() -> int
        {
            if(node == ROOT_NODE)
            {
                return 0;
            }
            if(s[parent[node]] == s[node])
            {
                return 0;
            }
            int longestDownPath = downPaths[parent[node]];
            for(node_t parentChild : children[parent[node]])
            {
                if(parentChild == node)
                {
                    continue;
                }
                if(s[parentChild] == s[parent[node]])
                {
                    continue;
                }
                longestDownPath = max(longestDownPath, 1 + upPaths[parentChild]);
            }
            return longestDownPath;
        }();

        /* pass the task to my children */
        for(node_t child : children[node])
        {
            fillDownPaths(parent, children, s, child);
        }
    }
public:
    int longestPath(const vector<node_t>& parent, const string& s) {
        const size_t numNodes = parent.size();
        upPaths = vector<int>(numNodes);
        downPaths = vector<int>(numNodes);
        vector<vector<node_t>> children{numNodes, vector<node_t>{}};


        for(node_t node = 1; node < numNodes; ++node)
        {
            children[parent[node]].push_back(node);
        }
        fillUpPaths(parent, children, s);
        fillDownPaths(parent, children, s);

        int longestPath = 0;
        for(node_t node = 0; node < numNodes; ++node)
        {
            longestPath = max(longestPath, upPaths[node] + downPaths[node]);
        }
        return longestPath;
    }
};
189813