Problem: somebody_elses_problem (2020 finals)

H Combinator (HC) is a business incubator that provides seed funding to startups. It operates on the core value that "nothing is somebody else's problem" (since businesses slow down when tasks get perpetually passed from person to person). HC currently supports \(T\) companies. As a managing director hoping to weed out some bad investments, you would like to assess how well the structure of each company holds up to this important principle.

Suppose a company has \(N\) employees, numbered \(1\) to \(N\) in decreasing order of seniority. Employee \(1\) is the CEO, while each other employee \(i\) \((i \ge 2)\) has a manager, employee \(M_i\) \((M_i \lt i)\).

When employee \(i\) is assigned a task to complete, they may instead reassign it to one of the following employees:

  1. One of their direct reports (any employee \(j\) such that \(M_j = i\)), if any exist
  2. Their manager (employee \(M_i\)), if \(i \ge 2\)
  3. The CEO (employee \(1\)), if \(i \ge 2\)

That employee may then reassign the task to yet another employee, and so on. However, an employee may never be reassigned a task that has ever been previously assigned to them, as the lack of responsibility would become too apparent. For example, an employee and manager cannot repeatedly pass a task back and forth.

Let \(R_i\) be the maximum number of times that a task could be reassigned from one employee to another if it were initially assigned to employee \(i\). For each company, you would like to calculate the product \((R_1 * R_2 * ... * R_N)\), modulo 1,000,000,007.

# Constraints

\(1 \le T \le 100\)
\(2 \le N \le 1,000,000\)
\(1 \le M_i \lt i\)

The sum of \(N\) across all companies is at most 6,000,000.


# Input

Input begins with an integer \(T\), the number of companies. For each company there are 2 lines. The first line contains the single integer \(N\). The second line contains \(N - 1\) space-separated integers, \(M_{2..N}\).


# Output

For the \(i\)th company, print a line containing *"Case #i: "*, followed by a single integer, the product of \(R_{1..N}\) modulo 1,000,000,007.


# Explanation of Sample

For the first company, if the CEO is initially assigned a task, all they can do is reassign it to one of their reports, who cannot then assign it back. On the other hand, if another employee is initially assigned a task, they can reassign it to the CEO, who can then assign it to the other remaining employee. Therefore, \(R = [1, 2, 2]\), and the final answer is (1 * 2 * 2) modulo 1,000,000,007 = 4.

For the second company, no matter which employee is initially assigned a task, it can then be reassigned twice. For example, employee 2 can assign their task to their report (employee 3), who can then assign it to the CEO. Therefore, \(R = [2, 2, 2]\).

For the third company, \(R = [2, 2, 3, 3]\).

For the fourth company, \(R = [3, 6, 6, 6, 7, 7, 7, 7, 8, 8]\).

For the fifth company, \(R = [4, 6, 6, 7, 8, 6, 7, 7, 8, 7, 7, 8, 8, 9, 9]\).


Sample input:
5
3
1 1
3
1 2
4
1 2 2
10
1 2 1 4 2 4 3 7 5
15
1 1 3 4 2 3 3 8 3 3 7 7 12 5


Sample output:
Case #1: 4
Case #2: 8
Case #3: 36
Case #4: 99574272
Case #5: 801542729


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


Code: // Somebody Else's Problem
// Solution by Jacob Plachta

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (auto i:s)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x < 0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x * x); }
string plural(string s) { return(Sz(s) && s[Sz(s) - 1] == 'x' ? s + "en" : s + "s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#define GETCHAR getchar_unlocked

bool Read(int& x) {
  char c, r = 0, n = 0;
  x = 0;
  for (;;) {
    c = GETCHAR();
    if ((c < 0) && (!r))
      return(0);
    if ((c == '-') && (!r))
      n = 1;
    else if ((c >= '0') && (c <= '9'))
      x = x * 10 + c - '0', r = 1;
    else if (r)
      break;
  }
  if (n)
    x = -x;
  return(1);
}

#define MOD 1000000007
#define LIM 1000001

int N, ans;
vector<int> ch[LIM];
int dyn1[LIM]; // max. len. of downward i -> leaf
int dyn2[LIM]; // max. len. of downward root -> leaf outside i's subtree
int dyn3[LIM]; // max. disjoint len. of downward root -> leaf plus other path ongoing from i's parent

void rec1(int i)
{
  // recurse, and compute dyn1[i]
  dyn1[i] = 0;
  Foxen(c, ch[i])
  {
    rec1(c);
    Max(dyn1[i], dyn1[c] + 1);
  }
}

void rec2(int i, int d)
{
  // compute answer for i
  ans = ans * (LL)max(dyn1[i] + dyn2[i] + (!i ? 0 : 1), dyn3[i]) % MOD;
  // compute max 2 (dyn1[c] + 1, c) pairs
  PR m1, m2;
  m1 = m2 = mp(0, -1);
  Foxen(c, ch[i])
  {
    PR p = mp(dyn1[c] + 1, c);
    if (p > m1)
      m2 = m1, m1 = p;
    else if (p > m2)
      m2 = p;
  }
  // compute dyn2[c] and dyn3[c], and recurse
  Foxen(c, ch[i])
  {
    int m = (m1.y == c ? m2 : m1).x;
    dyn2[c] = max(d + m, dyn2[i]);
    dyn3[c] = max(dyn3[i] + 1, dyn2[i] + m + 1 + (!i ? 0 : 1));
    rec2(c, d + 1);
  }
}

int ProcessCase()
{
  int i, j;
  // input
  Read(N);
  Fox1(i, N - 1)
  {
    Read(j), j--;
    ch[j].pb(i);
  }
  // DP
  ans = 1;
  rec1(0);
  rec2(0, 0);
  // reset
  Fox(i, N)
    ch[i].clear();
  return(ans);
}

int main()
{
  int T, t;
  Read(T);
  Fox1(t, T)
    printf("Case #%d: %d\n", t, ProcessCase());
  return(0);
}