Let \(K\) be the number of vertices with a medicine.

First, let’s think of how to solve when \(K \leq 1\). We can see that:

• If there is a monster we can defeat, we can defeat it right away to increase our strength, and gain access to the vertices behind it. This can be done by maintaining a priority queue of accessible monsters sorted by increasing strength, and checking whether we can defeat the weakest monster.
• If there is a medicine, it is optimal to wait as long as possible before taking it (i.e. when there are no more monsters that we can defeat), as it means we have more strength to multiply.

For \(K > 1\), it’s also optimal to delay taking any medicine, but we could run into the possibility of there being more than one medicine we can access by the time we should take one. It is not obvious which medicine to take next, as it is hard to determine the effect of the monsters and medicine behind each of the considered medicine.

One idea might be to brute force all \(K!\) potential permutations of medicine, but \(O(K! N \log N)\) time seems quite risky.

Instead, let’s use bitmask. Let \(dp [S]\) be the maximum strength achievable after taking the medicines in mask/set \(S\). (To ease implementation, we could add a fake medicine to vertex \(1\) with \(g_1 = 1\)). We also store up to one “game state” for each \(dp\) entry, which are the data structures containing the medicines and undefeated monsters currently accessible.

When iterating through the masks, we can “load” the game state for that mask if it exists. Then for each available medicine, we copy the game state before taking that medicine, then defeat as many monsters as possible, and then update the corresponding \(dp\) entry. We only “save” the game states that correspond to the maximum strength for each mask. This is because two states with the same mask implies the same set of vertices that aren’t blocked by untaken medicines, and the state with the higher strength implies that we’ve defeated at least as many monsters, and that our strength would be higher after taking the next medicine.

Do note that our strength value might overflow a standard integer type, but we could fix that by “capping” the strength, as we don’t need strength more than the strongest monster in the tree.

The problem is therefore solved in time complexity \(O(2^K K N \log N)\) or so.