In the first and second subtasks, we can observe that the pairs of friends form a single chain. We will solve the first subtask using dynamic programming which in its state has a position in the chain ~P~, the amount of džumbus we have at our disposal ~K~ and a binary flag ~B~ which denotes whether person at position ~P~ exchanged any solutions. The value ~dp[P][K][B]~ reflects on only the first ~P~ people in the chain and it will denote the largest number of people that can exchange solutions with optimal distribution of leftover drink when it is also known (via ~B~) whether person at position ~B~ has already done so. The general idea behind the transition is the following:

$$\displaystyle \begin{align*} dp[P][K][0] &= \max\{dp[P-1][K][0], dp[P-1][K][1]\} \\ dp[P][K][1] &= \max\begin{cases} dp[P-1][K-D_{L[P]}][1]+1 \\ dp[P-1][K-D_{L[P]}-D_{L[P-1]}]+2 \end{cases} \end{align*}$$

The answer to query ~S_i~ equals to ~\max\{dp[L[N]][S_i][0], dp[L[N]][S_i][1]\}~. The time complexity of this solution is ~\mathcal O(N \max S_i)~.

Since there is no additional constraint on value ~S_i~ in the second subtask, the dp solution from the first subtask would not fit the time and memory constraints. Luckily, we can think about the same thing in a different light. We will again store the position ~P~ in our state and a binary flag ~B~ which have the same meaning as before. But now, the amount of džumbus will be the value of our dp and the number of people that have exchanged the solutions will be moved to the state. The transitions are left as an exercise to the reader.

The answer to the query ~S_i~ is the largest ~R~ such that ~\min\{dp[L[N]][R][0], dp[N][R][1]\} \le S_i~. The complexity of this solution is ~\mathcal O(N^2)~.

In the third subtask we don't have a chain, but a forest. A forest can be reduced to a single tree by introducing a dummy root node which we treat as a person with infinite ~D_i~. In that way, we are sure that person does not affect the results.

We use a similar dynamic programming solution as in the second subtask, except we do it on a rooted tree. The value of ~dp[P][R][B]~ is the smallest amount of džumbus we need to make ~R~ people that are in ~P~'s subtree to exchange solutions when it is also known whether ~P~ exchanged the solutions (bit ~B~). When calculating the dp values for subtree ~P~, we assume we already have all the dp values calculated for the entire subtree. We will also have an auxiliary ~dp\_prefix~ which in its state holds the number of people in a subtree of ~P~ which have exchanged solutions at least once, as well as number ~K~ which denotes that we have taken into consideration the first ~K~ children of ~P~ thus far. Then, it is obvious that ~dp[P][R][B] = dp\_prefix[R][B][\text{number of children of }P]~. Let ~C[i]~ denote the ~i^\text{th}~ child of node ~P~. The transitions are therefore:

$$\displaystyle \begin{align*} dp\_prefix[R][0][K] &= \min_{A+B=R} \{dp\_prefix[A][0][K-1] + \min\{dp[C[K]][B][0], dp[C[K]][B][1]\}\} \\ dp\_prefix[R][1][K] &= \min_{A+B=R} \begin{cases} dp\_prefix[A-1][0][K-1] + D_P + dp[C[K]][B][1] \\ dp\_prefix[A-1][0][K-1] + D_P + dp[C[K]][B-1][0] + D_{C[K]} \\ dp\_prefix[A][1][K-1] + D_P + dp[C[K]][B][1] \\ dp\_prefix[A][1][K-1] + D_P + dp[C[K]][B-1][0] + D_{C[K]} \\ dp\_prefix[A][1][K-1] + dp[C[K]][B][0] \end{cases} \end{align*}$$

(Implementation details and corner cases should be carefully analyzed by the reader)

When we add up all the states across all of the nodes, we get a total of ~\mathcal O(N^2)~ states in the ~dp\_prefix~ and every transition is calculated in at most ~\mathcal O(N)~ steps. Therefore, the complexity can be bounded by ~\mathcal O(N^3)~.

I know what you're thinking. There is no way this can be optimized any further.

To solve the fourth and final subtask you should note that, with careful implementation, the complexity of our solutions is in fact ~\mathcal O(N^2)~. Obviously, it is impossible that a set of people exchanges more solutions than the size of that set. Therefore, when calculating ~dp\_prefix~, it is not necessary to check all options for ~A~ and ~B~, just those which are possible (~A~ cannot be larger than the sum of subtree sizes for already processed children increased by ~1~ and ~B~ cannot be larger than the subtree size of the current child). We will prove that the total complexity of dp calculations for each subtree is at most ~\mathcal O(\text{subtree size}^2)~. The proof inducts on the tree depth. The claim obviously holds for leaves. Let's fix a node and suppose we have calculated dp values for its children with the mentioned complexity. Suppose that node has ~x~ children with subtree sizes ~Y_1, Y_2, \dots, Y_X~. The total complexity for calculating dp values of that node and its subtree can be expressed as:

$$\displaystyle \begin{align*} \mathcal O\left(\sum_{i=1}^X Y_i^2 + \sum_{i=1}^X \left(1+\sum_{j=1}^{i-1} Y_j\right)Y_i\right) &= \mathcal O\left(\sum_{i=1}^X Y_i^2 + \sum_{i=1}^X Y_i + \sum_{i=1}^X \sum_{j=1}^{i-1} Y_i Y_j\right) \\ &= \mathcal O\left(1 + \sum_{i=1}^X Y_i^2 + 2\sum_{i=1}^X Y_i + 2\sum_{i=1}^X \sum_{j=1}^{i-1} Y_i Y_j\right) \\ &= \mathcal O\left(\left(1+\sum_{i=1}^X Y_i\right)^2\right) \\ &= \mathcal O(\text{subtree size}^2) \end{align*}$$

The total time complexity of the whole solution is therefore ~\mathcal O(N^2)~.