← All solutions

First, note that each castle can be described by two parameters: first the number of soldiers “consumed” when conquering this castle (i.e., the number of soldiers who will die plus the number of soldiers that need to be left there afterwards) and second the number of soldiers needed to attack the castle (i.e., the maximum of the a parameter and the number of soldiers consumed).

Now, let us consider the case when the underlying graph of paths is a complete graph, instead of a tree as in the problem. In this case, one should simply choose the order to conquer the castles greedily, taking the one with largest (#attackers − #consumed) first (with ties broken arbitrarily). This is an intuitively appealing solution and it is not hard to prove that it is optimal.

Finally, when the underlying graph is a tree, as in the problem, the solution is as follows. We try all possible choices of castles as the first castle to conquer, and root the tree at this particular castle. At each castle, we have to decide in which order to conquer the different subtrees rooted at the children. But this we can do using the greedy approach above: we are free to visit the children in any order, and we can think of each subtree as collapsing to a single vertex consuming a certain number of soldiers (simply the sum of the soldiers consumed over all castles in the subtree) and requiring a certain number of attackers (which we can compute recursively).