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

    //can think of this as connected component, edges between nodes of adjacent just can't be reached, delete edge
    //then within each go as far as you can???
    //node is connected only to parent and to children. If parent is same letter, child is now root. If child is same, disconnect it
    //disconnecting simply means updating the parent array, looking at node i, i parent is parent[i] if s[parent[i]] == s[i] then we set
    // parent[i] = -1, no parent. Now, we can dfs from each root of connected and see how far we can go??
    
    int longestPath(vector<int>& parent, string s) {
        unordered_map<int, vector<int>> graph;

        for (size_t i = 0; i < parent.size(); i++) {
            if(parent[i] >= 0 && s[i] == s[parent[i]]) {
                //disconnect
                parent[i] = -1;
            }
            if(parent[i] >= 0) {
                //parent now connected to child
                graph[parent[i]].push_back(i);
            }
        }

        // for (const auto& [parent, vec] : graph) {
        //     cout << parent << ": ";
        //     for (const auto& child : vec) {
        //         cout << child << " ";
        //     }
        //     cout << endl;
        // }
        //ok now graph is disconnected. call dfs on each root and see the longest returned
        //need to construct graph first. each node is connected to it's children and parents. each node knows its parent but
        // no node knows it's children.
        //for each connected component, my recursive step should propagate up the length of the longer child + 1. I should update
        // my global max path with left child len + right child len

        int global_max = 1;
        for (int i = 0; i < parent.size(); i++) {
            if (parent[i] == -1) {
                dfs(graph, i, global_max);
            }
        }
        //cout << endl;
        return global_max;
    }

    int dfs(const unordered_map<int, vector<int>>& tree, int current, int& global_max) {
        if(tree.find(current) == tree.end() || tree.at(current).empty()) {
            //no children gang
            return 1;
        }
        //otherwise, recurse and propagate up the max
        int max_child = 0;
        int max_child_len = 0;
        int second_max_child_len = 0;
        int total_child_len = 0;

        const auto& children = tree.at(current);

        for (const auto& child : children) {
            int child_len = dfs(tree, child, global_max);
            if (child_len > max_child_len) {
                second_max_child_len = max_child_len;
                max_child_len = child_len;
                max_child = child;
            }
            if (child_len > second_max_child_len && child != max_child) {
                second_max_child_len = child_len;
            }
        }
        //cout << current << " max_len: " << max_child_len << " second_max_len: " << second_max_child_len << endl;
        //i need to tell parent that my length is max(left_len, right_len) + 1
        //at each level, see if the left + right + 1 path is maximal

        global_max = max(max_child_len + second_max_child_len + 1, global_max);
        return 1 + max(max_child_len, second_max_child_len);
    }
};
187516