Let's look at the vertices, which causes maximum damage. Adoption: we remove the vertex immediately after the remove of her father. If we know two unequivocal order of vertices, then try to get them to merge and reduce the number of vertices to 1. We can do this because we know that we will remove these vertices in that order. Another statement, if we started to remove some component with dependencies, then we will remove it all, without having to switch to other components.

Now we calculate how much damage we obtain from the removal of the components size bed and the total damage sum. size * sum for this size moves. We compare the two components and understand in what order better to remove them.

In the first case size1 * sum1 + (size1 + size2) * sum2. Second size2 * sum2 + (size1 + size2) * sum1. Let's compare them. We find that quite compare: sum / size.

Now, we will support the entire structure in the set, for a maximum. And dsu for mergers

@-Wave-, I agree with you, next time, I will try to discard the tedious part which is not highly related to the algorithm. Because I got AC the first time very easily, so I haven't noticed that there is any problem.

Let's transform the given problem to the next one:

for i1 = 1 .. n
  for i2 = i1 .. n
    ....
     for ik = i(k - 1) .. n

This problem can be solved with k-combination with repetitions
(I strongly belive, you can understand why this is the answer).

In order to transform initial problem to the problem above,
you have to extract from initial N the values from 1 to k - 1 which is .

Now, you can get the formula from editorial.

I read the editorial after the contest and i bounded the logic chain today in the morning.

There is an easy way to understand the formula.

We'll map each sequence (i₁, i₂, ..., i_k) with a new sequence (a₁, a₂, ..., a_k, a_k + 1, such that a₁ = i₁, a₂ = i₂ - i₁, a₃ = i₃ - i₂ - 1, ..., a_k = i_k - i_k - 1 - (k - 2), a_k + 1 = n - (i₁ + i₂ + ... + i_k) + 1. Now, and note that a_i are positive integers. Conversely, every positive integer solution to this equation is equivalent to a sequence (i₁, i₂, ..., i_k) that can be attained in the code. So, we just need to count the number of new sequences, which is easy, since by balls in urns formula this is just . This gives the formula.

I found another blog regarding this problem .

The problem seems to be the same as this problem (just stated in a different manner).

This should help you solve the problem.

Thanks both of you. I will read the explanations you gave, but I'm optimist that I will understand at least one of them as they seem to be written very well.