hackercupai/hackercup huggingface dataset:
The employees can be considered nodes of a tree rooted at node 1 (the CEO), with each node \(i\)'s set of children \(C_i\) consisting of all nodes \(j\) such that \(M_j = i\). We'll additionally let \(D_i\) be the depth of node \(i\), and \(S_i\) be its set of siblings.

We can observe that \(R_i\) corresponds to either of the following:

- The maximum length of any single simple path starting at node \(i\) (potentially going upwards to some ancestor and then back downwards)
- 1 plus the maximum combined length of any node-disjoint pair of simple paths, the first one starting at node \(i\) (potentially going upwards to some ancestor and then back downwards) and the second starting at the root (and only going downwards)

We'll approach computing these lengths and sums with dynamic programming.

First, let \(\textit{DP1}_i\) be the maximum length of any path starting at node \(i\) and contained within \(i\)'s subtree. \(\textit{DP1}_{1..N}\) may be computed in standard fashion based on the recurrence \(\textit{DP1}_i = \max(c \in C_i | \textit{DP1}_c + 1)\).

Next, let \(\textit{DP2}_i\) be the maximum length of any path starting at the root and never entering node \(i\)'s subtree. If \(i\) is the root, then \(\textit{DP2}_i = 0\). Otherwise, \(\textit{DP2}_i = \max(D_{M_i} + \max(s \in S_i | \textit{DP1}_s + 1), \textit{DP2}_{M_i})\).

Now, let \(\textit{DP3}_i\) be 1 plus the maximum combined length of any node-disjoint pair of simple paths, the first one starting at node \(i\) but not including any of \(i\)'s children, and the second starting at the root. If \(i\) is the root, then \(\textit{DP3}_i = 0\). Otherwise, \(\textit{DP3}_i = \max(\textit{DP3}_{M_i} + 1, \textit{DP2}_{M_i} + \max(s \in S_i | \textit{DP1}_s + 1) + 2)\).

Finally, if \(i\) is the root, then \(R_i = \textit{DP1}_i\). Otherwise, \(R_i = \max(\textit{DP1}_i + \textit{DP2}_i + 1, \textit{DP3}_i)\).

We can compute all of the above values in \(O(N)\) time through two recursive (or iterative) passes over the tree.