<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 res = 0;
    // returns the longest path that can be formed from the given node
    int dfs(vector<vector<int>>& adj, vector<bool>& vs, string& s, int currnode) {
        if (vs[currnode]) {
            return 0;
        }
        vs[currnode] = true;
        vector<int> children = adj[currnode];
        // for (int c : children) {
        //     cout << c << " ";
        // }
        // cout << endl;
        int fmx = -1, smx = -1; // track the max child length
        int fn = -1, sn = -1; // track the id of the child
        for (int child : children) {
            int childlen = dfs(adj, vs, s, child);
            // cout << childlen << endl;
            if (s[child] == s[currnode]) continue;
            if (childlen > fmx) {
                smx = fmx, sn = fn;
                fmx = childlen, fn = child;
            } else if (childlen > smx) {
                smx = childlen, sn = child;
            }
        }
        // cout << "currnode: " << currnode << endl;
        // cout << fmx << " " << smx << endl;
        // cout << "----" << endl;
        // try to connect
        if (fmx != -1 && smx != -1) {
            // case where can connect the two
            if (s[fn] != s[currnode] && s[sn] != s[currnode]) {
                res = max(res, fmx + smx + 1);
            } else if (s[fn] != s[currnode]) { // case where can connect first max
                res = max(res, fmx + 1);
            } else if (s[sn] != s[currnode]) {
                res = max(res, smx +1);
            } else {
                res = max(res, 1);
            }
            // return the longest path u can form
            return max(fmx + 1, smx + 1);
        } else if (fmx != -1) { // case where only 1 max
            // case where can connect
            if (s[fn] != s[currnode]) {
                res = max(res, fmx + 1);
            } else {
                res = max(res, 1);
            }
            return fmx + 1;
        } else { // case where no max nor second max
            res = max(res, 1);
            return 1;
        }
    }
    int longestPath(vector<int>& parent, string s) {
        int n = parent.size();
        vector<vector<int>> adj(n);
        for (int node = 0; node < n; ++node) {
            int p = parent[node];
            if (p == -1) {
                continue;
            }
            adj[node].push_back(p);
            adj[p].push_back(node);
        }
        vector<bool> vs(n, false);
        dfs(adj, vs, s, 0);
        return res;
    }
};
263293