1 . We cut off all white branches. Later we will need some of them, so we need to have e.g. either 1) a copy of an initial graph, or 2) save these white branches to a new graph, which is more efficient way, or 3) we can color branches instead of cutting. Additionally we need to save a node to which a particular cut branch is adjacent. But if a branch is adjacent to a black node we also can drop it, because we have an obvious answer: from all nodes of that branch we can move to the black node. Cutting a white branch is simple loop: we remove white leafs until there are no white leafs left.

The remaining graph has all of its leafs black.

2 . Now we can check if there are any three black nodes on the same way. If so then we can move to black node from any point of the graph. If not then we need to process further. Simplest way to check that — compare the number of leafs with the number of overall black nodes.

There is also the case when the number of black leafs is more then 2 and one of the black leafs is adjacent to a node which has more than two edges. Answer is 'all 1', because that leaf attracts to itself from any of 2+ branches with the help of another branch.

3 . If we haven't obtained an answer 'all 1', then our graph can be seen as this:

[k_1,1]    [k_2,2]      [k_m,m]
   |          |    ...    |
(k_1-1,1) (k_2-1,2)   (k_m-1,m)
   |          |    ...    |
   :          :           :
   |          |    ...    |
 (1,1)      (1,2)       (1,m)
   |          |    ...    |
  <       white tree       >

where square brackets mark black nodes, parentheses mark white nodes, $$$m$$$ is a number of black leafs, and all $$$k_i \ge 2$$$.

We can see that it is possible to move to black nodes only from the adjacent nodes: $$$(k_i-1,i), i = 1 \dots m$$$. All these adjacent nodes are unreachable from the rest of the tree because they have only one attractor leaf on their branch ($$$i$$$), and $$$m-1 \ge 1$$$ detractors from other branches.

4 . Now we check for all nodes with zero answer if it is adjacent to previously cut branch (step 1). If so then all that branch has also zero answer. Implementing e.g. with BFS.

We will consider an extra first monster at second $$$1$$$ with health $$$0$$$.

We might need more than the monster's health to kill it because we have to wind up to kill stronger ones later. More particularly, in order to kill $$$i-th$$$ monster with $$$x$$$ mana, we must kill $$$(i-1)-th$$$ monster with no less than $$$x-(k[i] - k[i - 1])$$$ mana. So it is possible to set $$$h[i]$$$ to $$$max(h[i],h[i+1]+k[i]-k[i+1])$$$, with $$$i=n-1,n-2,\dots , 1,0$$$. Then the following condition holds: "For every $$$0 \leq i \leq n - 1$$$, if we kill $$$i-th$$$ with $$$h[i]$$$ mana, we can also kill $$$(i+1)-th$$$".

Then, we only need to calculate the real mana used to kill $$$(i + 1)-th$$$ monster after killing the $$$i-th$$$ one. Firstly we check if it's possible to start from $$$1$$$ the next step and wind up. We can achieve that by using variable step denoting the counts of steps we have before encountering the next monster. If step is not less than $$$h[i+1]$$$, then we can, otherwise we cannot. If we can't, the only option is to start from the current mana.

First, sort all numbers and then make a new array $$$b$$$ that stores the frequencies of each unique number.

Let $$$ f(x) = 2^{\lceil log_2x \rceil}, g(x) = f(x) - x, sum_{l,r} = \sum\limits_{i=l}^rb_i$$$

The new array can be partitioned into AT MOST 3 subarrays and in the cases that we use only 2/1 subarrays, we need to make up for it by bringing in 1/2 persons.

$$$dp[i][j] =$$$ answer if we consider the first $$$i$$$ numbers and divide it into $$$j$$$ subarrays

Base case: $$$dp[i][1] = g(sum_{1,i})$$$

It's easy to see that $$$dp[i][k] = min(dp[j][k-1] + g(sum_{j+1,i})), j < i, 2 \leq k \leq 3$$$

This is $$$O(n^2logn)$$$ and is too slow, but it can be sped up.

Notice, $$$sum_{j+1,i} = sum_{1,i}-sum_{1,j}$$$

$$$dp[i][k] = min(dp[j][k-1] + g(sum_{1,i}-sum_{1,j}))$$$

$$$dp[i][k] = min(dp[j][k-1] + f(sum_{1,i}-sum_{1,j})+sum_{1,j})-sum_{1,i}$$$

Actually, $$$f(sum_{1,i}-sum_{1,j})$$$ changes at most $$$logN$$$ times and therefore the array can be grouped into at most $$$logN$$$ groups based on those changes.

Let $$$f(sum_{1,i}-sum_{1,j}) = 2^x $$$ for some $$$0 \leq x \leq logN$$$

Then: $$$ 2^{x-1} < sum_{1,i}-sum_{1,j} \leq 2^x$$$ and with simple math we get:

$$$ sum_{1,i}-2^x \leq sum_{1,j} < sum_{1,i}-2^{x-1}$$$

So we can see that all $$$j$$$ that satisfy this inequality are in the same group $$$x$$$ and also consecutive.

We then brute-force for all $$$x$$$ and for a fixed $$$k$$$, try to get the minimum $$$dp[j][k]$$$ such that $$$sum_{1,j}$$$ is in the desired range. This is clearly RMQ and can be done with segment trees(Note: You need $$$k-1$$$ different segment trees for each $$$k$$$ in the dp transition, in this case $$$k=3$$$ since we are dividing into at most 3 subarrays).

Solution