Problem: perf-ore-mance (2021 round3)

Facebulk Inc. is a mining company that's about to release its latest performance report. In these trying times, accurate numbers will be crucial. As a forensic accountant, you've been hired to secretly audit employee earnings across \(T\) ore-processing plants.

A given plant has \(N\) employees. Employee \(1\) is the superintendent, and has no manager. Each other employee \(i\) has a single direct manager, employee \(M_i\) (\(1 \le M_i < i\)). With access to the HR database, you have full knowledge of the company structure.

The HR database also contains each employee's individual earnings in dollars, which is possibly zero or negative (if the employee lost money). However, the database's anonymization scheme prevents you from directly looking up an employee's individual earnings, instead supporting the following two types of queries which may be performed as many times as you like:

  1. For a given employee \(i\), query the sum of the earnings of all employees *directly managed* by employee \(i\) (only allowed if there are at least \(K\) such employees)
  2. For a given employee \(i\), query the sum of the earnings of all employees *either directly or indirectly managed* by employee \(i\) (only allowed if there are at least \(K\) such employees)

Despite the indirect nature of these queries, with each result being the sum of earnings of at least \(K\) employees, you may still be able to infer some earnings of individual employees.

However, you're not necessarily satisfied with that. As a proficient hacker, you've figured out how to drop employees from the HR database. Before performing any queries, you may choose to delete \(0\) or more employees (along with their earnings) from the company structure and database. You can only delete an employee if they do not directly manage anyone still in the database at the time.

Assuming you optimally decide which employees to delete and make the most of the database queries, what's the maximum possible number of employees whose earnings you can determine?


# Constraints

\(1 \le T \le 60\)
\(1 \le N \le 800{,}000\)
\(2 \le K \le 10\)
\(1 \le M_i < i\)

The sum of \(N\) across all plants is at most \(4{,}000{,}000\).


# Input

Input begins with an integer \(T\), the number of ore-processing plants. For each plant, there is first a line containing \(2\) space-separated integers, \(N\) and \(K\). Then, there is a second line containing \(N-1\) space-separated integers \(M_{2..N}\).


# Output

For the \(i\)th plant, print a line containing *"Case #i: "* followed by a single integer, the maximum possible number of employees whose earnings you can determine after a round of deletions.


# Sample Explanation

In the first plant, the company structure looks as follows:

{{PHOTO_ID:575117230498780}}

If you don't delete any employees, you can determine the earnings of employee \(2\) as follows. If \(\$X\) is the result of query type 2 for employee \(1\) (the sum of employee \(2\), \(3\), and \(4\)'s earnings), and \(\$Y\) is the result of query type 1 for employee \(2\) (the sum of employee \(3\) and \(4\)'s earnings), then employee \(2\)'s earnings must then be equal to \(\$X - \$Y\). No other employees' earnings can be determined.

In the second plant, the company structure looks as follows:

{{PHOTO_ID:281780436953175}}

One option is to delete employees \(3\), \(5\), and \(7\). This yields a company structure just like the one in the first plant, with employee \(2\)'s earnings becoming possible to determine. It's impossible to simultaneously determine multiple employees' earnings.

In the third plant, the only value which may be queried is the sum of the earnings of employees \(2\), \(3\), \(4\), and \(5\) (and only if none of them are deleted). This does not allow any individual employee's earnings to be determined.




Sample input:
7
4 2
1 2 2
7 2
1 1 2 3 2 3
5 4
1 1 1 1
6 2
1 2 2 4 5
6 5
1 2 2 4 5
20 3
1 1 2 1 1 4 3 6 4 9 8 6 11 11 10 5 5 14 6
40 4
1 1 2 1 3 1 3 4 5 5 7 5 8 2 6 10 5 12 8 16 6 6 4 22 24 6 18 7 26 22 15 6 22 30 25 30 32 21 35


Sample output:
Case #1: 1
Case #2: 1
Case #3: 0
Case #4: 2
Case #5: 0
Case #6: 4
Case #7: 7


Solution: The company structure can be thought of as a tree rooted at node (employee) \(1\), with nodes' labels being employees' earnings. Given such a fixed tree, let \(P_i\) be node \(i\)'s parent, \(C_i\) be the number of children of node \(i\), \(S_i\) be the number of nodes in node \(i\)'s subtree (including \(i\)), \(Q_1(i)\) be the result of query type 1 for node \(i\) (valid if \(C_i \ge K)\), and \(Q_2(i)\) be the result of query type 2 for node \(i\) (valid if \(S_i > K\)).

There are then only two possible types of situations in which a node \(i\)'s label can be determined:

  1. Letting \(x = P_i\), \(C_x = 1\) and \(S_i > K\). Node \(i\)'s label is then equal to \(Q_2(x) - Q_2(i)\).
  2. Letting \(x = P_{P_i}\), \(C_x \ge K\), \(S_{P_i} = 2\), and for each other child \(c\) of \(x\) (aside from \(P_i\)), either \(S_c = 1\) or \(S_c > K\). Node \(i\)'s label is then equal to \(Q_2(x) - Q_1(x)\), minus \(Q_2(c)\) for each child \(c\) of \(x\) for which \(S_c > K\).

It can be shown that no other relevant situations exist, with a node \(i\)'s label only inferable based on queries from its parent or grandparent (as described above), and never based on queries from higher-up ancestors. Given a node \(x\) with a child \(c\), \(Q_1(x)\) and \(Q_2(x)\) cannot provide information which distinguishes different descendants of \(c\) from one another – at best, the label sum of all of \(c\)'s descendants can be determined, which is only useful when \(c\) has exactly one descendant (this is situation #2). If \(c\) has at least \(K\) descendants, then this sum is equivalent to \(Q_2(c)\) anyway, while if \(c\) has between \(2\) and \(K-1\) descendants (inclusive), then this sum can't be combined with any other valid queries and is useless.
  
Note that it's impossible for both situations to apply to the same node \(i\) (as it can't have both \(0\) siblings and at least \(K-1\) siblings). It's similarly impossible for an ancestor node \(x\) to be involved in multiple situations (as it can't have both \(1\) child and at least \(K\) children).

We'll proceed with a dynamic programming approach in which we'll effectively consider all possible subsets of nodes to delete from the tree while counting and maximizing the number of situation occurrences (in other words, the number of nodes whose labels can be determined).

Let \(DP[x][y]\) be the maximum number of situation occurrences when only considering node \(x\)'s subtree, such that \(S_x = y\) (or such that \(S_x > K\) if \(y = K+1\), as we don't care about the exact subtree size once it exceeds \(K\)). There are \(O(NK)\) such states, with the maximum value of \(DP[1][1..(K+1)]\) being our final answer.

For each node \(x\), when computing \(DP[x][0..(K+1)]\) based on the \(DP\) values of \(x\)'s children, the following cases all need to be accounted for:

  - *Assuming that only situation 1 will apply:* \(DP[x][K+1]\) can equal \(DP[c][K+1] + 1\) for any child \(c\)
  - *Assuming that only situation 2 will apply:* We can employ a secondary level of \(DP\) with states of the form \((f, s)\), maximizing the number of situation occurrences after considering the first \(f\) children, such that \(S_x = s\) so far (\(0 \le f \le C_x\), \(1 \le s \le K+1\))
  - *Assuming that neither situation will apply:* We can employ another round of \(DP\) with states of the form \((f, c, z)\), maximizing the number of situation occurrences after considering the first \(f\) children, with \(c\) children included so far, one of which has a subtree size of \(2\) if \(z = 1\), and the rest of which have subtree sizes of either \(1\) or at least \(K+1\) (\(0 \le f \le C_x\), \(0 \le c \le C_x\), \(0 \le z \le 1\)).
  
The dynamic programming described above can be implemented in a total of \(O(NK^2)\) time.

[See David Harmeyer (SecondThread)'s solution video here.](https://youtu.be/CVOKepmfXM4)


Code: #include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

const int LIM = 800002;
const int MAXK = 10;

int N, K;
vector<int> children[LIM];

// dp[i][j] = max # of guessable nodes only considering i's subtree,
//            such that i's subtree size is j (with j capping out at K + 1)
int dp[LIM][MAXK + 2];

// dp2[s] = max # of guessable nodes only considering current node's subtree
//          such that its subtree size is s (with s capping out at K + 1)
int dp2[MAXK + 2];

// dp3[a][b] = max # of guessable nodes only considering current node's subtree
//             such that it has a children (with a capping out at K)
//             one of which has subtree size 2 if and only if b = 1,
//             and the rest of which have subtree sizes either 1 or > K
int dp3[MAXK + 1][2];

void rec(int i) {
  // Recursively compute children's DP values.
  for (int c : children[i]) {
    rec(c);
  }
  // Use children's DP values.
  memset(dp2, -1, sizeof dp2);
  memset(dp3, -1, sizeof dp3);
  dp2[1] = dp3[0][0] = 0;
  for (int c : children[i]) {
    // Assume no new guessable nodes.
    for (int s1 = K + 1; s1 >= 1; s1--) {
      int d1 = dp2[s1];
      if (d1 >= 0) {
        for (int s2 = 1; s2 <= K + 1; s2++) {
          int d2 = dp[c][s2];
          if (d2 >= 0) {
            int s = min(K + 1, s1 + s2);
            dp2[s] = max(dp2[s], d1 + d2);
          }
        }
      }
    }
    // New guessable node, situation 1:
    // - Node i has 1 child
    // - That child's subtree size is > K (that child is guessable)
    int d1 = dp[c][K + 1];
    if (d1 >= 0) {
      dp[i][K + 1] = max(dp[i][K + 1], d1 + 1);
    }
    // New guessable node, situation 2:
    // - Node i has at least K children
    // - One child's subtree size is exactly 2 (that child's single child is
    // guessable)
    // - Each other child's subtree size is either exactly 1, or > K
    for (int a1 = K; a1 >= 0; a1--) {
      for (int b1 : {1, 0}) {
        d1 = dp3[a1][b1];
        if (d1 >= 0) {
          int a2 = min(K, a1 + 1);
          int d2 = max(dp[c][1], dp[c][K + 1]);
          if (d2 >= 0) {
            dp3[a2][b1] = max(dp3[a2][b1], d1 + d2);
          }
          if (!b1 && (d2 = dp[c][2]) >= 0) {
            dp3[a2][1] = max(dp3[a2][1], d1 + d2);
          }
        }
      }
    }
  }
  // Merge sub-DP results into main DP.
  for (int s1 = 1; s1 <= K + 1; s1++) {  // No new guessable nodes.
    dp[i][s1] = max(dp[i][s1], dp2[s1]);
  }
  int d1 = dp3[K][1];
  if (d1 >= 0) {  // New guessable node, situation 2.
    dp[i][K + 1] = max(dp[i][K + 1], d1 + 1);
  }
}

int solve() {
  for (int i = 0; i < N; i++) {
    children[i].clear();
  }
  // Input.
  cin >> N >> K;
  for (int i = 1; i < N; i++) {
    int p;
    cin >> p;
    children[p - 1].push_back(i);
  }
  // Tree DP.
  memset(dp, -1, sizeof(dp[0]) * N);
  rec(0);
  // Compute answer.
  int ans = 0;
  for (int i = 1; i <= K + 1; i++) {
    ans = max(ans, dp[0][i]);
  }
  return ans;
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}