## Editorial for Yet Another Contest 8 P3 - Herobrine

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Author:

### Subtask 1

The answer for a given value of is the maximum strength of a Herobrine created from the ores in node 's subtree. For this subtask, it suffices to solve the problem individually for each value of , so let's consider a given multiset of ores and determine the maximum strength of a Herobrine created from it.

We only care about the frequency of each ore, so let be the list of non-zero frequencies sorted in non-increasing order. If we fix the size of as , then Herobrines can be created using the first crafting recipe. It follows that the answer is .

**Time Complexity:**

### Subtask 2

In this subtask, the tree is a line. This means we can solve for each from down to , provided that we can add ores to current multiset and maintain the answer.

Let be the frequency of ore , and be the number of satisfying . It is easy to see that the answer can also be expressed as . Now, consider what happens when ore is added to the multiset. is first incremented, then is incremented, and the answer is the maximum of the previous answer and . This allows us to maintain the answer in time whenever an ore is inserted.

**Time Complexity:**

### Subtask 3

Apply the small-to-large merging optimisation on the tree combined with the technique from subtask 2. Note that we can compare either subtree sizes or the total number of ores in each subtree; either works.

It's worth noting that it is possible to implement a solution in memory, without any maps, yielding a much better constant factor. This relies on the fact that the same time complexity can be reached if the ores in the current node are always swapped only with the ores in the subtree of the heaviest child. Keep global arrays for and . When performing a DFS search of a subtree, the heaviest child should be searched last. Before the heaviest child is searched, and should be reset, so that after the heaviest child is searched, and contain the ores in the heaviest child's subtree, as desired. The remaining ores in the subtree can now be added one by one.

**Time Complexity:** or

## Comments