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)