<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>& parent, string global_s) {
        s = global_s;
        int n = s.size();
        g.resize(n);
        for (int i = 0; i < n; i++) {
            g[i].clear();
        }
        for (int i = 1; i < n; i++) {
            g[i].push_back(parent[i]);
            g[parent[i]].push_back(i);
        }
        f_down.resize(n, 0);
        f_up.resize(n, 0);
        visited.resize(n, 0);
        f_down[0] = 1;
        dfs_down(0);
        for (int i = 0; i < n; i++) {
            visited[i] = 0;
        }
        f_up[0] = 0;
        dfs_up(0);
        return ans;
    }
    vector < vector <int >> g;
    vector < int > f_up;
    vector < int > f_down;
    vector < short > visited;
    string s;
    int ans = 1;

    void dfs_up(int v) {
        visited[v] = true;
        //ans = max(ans, f_up[v] + 1);
        int ma1 = 0;
        int ch1 = -1;
        int ma2 = 0;
        int ch2 = -1;
        for (int child: g[v]) {
            if (!visited[child] && s[child] != s[v]) {
                if (f_down[child] >= ma1) {
                    ma2 = ma1;
                    ch2 = ch1;
                    ma1 = f_down[child];
                    ch1 = child;
                } else if (f_down[child] >= ma2) {
                    ma2 = f_down[child];
                    ch2 = child;
                }
            }
        }
        ans = max(ans, ma1 + ma2 + 1);
        for (int child : g[v]) {
            if (!visited[child]) {
                if (s[child] != s[v]) {
                    f_up[child] = max(f_up[child], f_up[v] + 1);
                    if (child != ch1 && ch1 != -1) {
                        f_up[child] = max(f_down[ch1] + 1, f_up[child]);
                    }
                    if (child != ch2 && ch2 != -1) {
                        f_up[child] = max(f_down[ch2] + 1, f_up[child]);
                    }
                }
                dfs_up(child) ;   
            }
        }
    }

    void dfs_down(int v) {
        visited[v] = true;
        f_down[v] = 1;
        for (int child : g[v]) {
            if (!visited[child]) {
                dfs_down(child);
                if (s[child] != s[v]) {
                    f_down[v] = max(f_down[v], f_down[child] + 1);
                }
            }
        }
    }
};
210479