Can anyone explain me how to solve Snakes capturing the Mongoose Cities problem ?
I approached this problem through DP. I had 2 different DP’s DPa[node] and DPb[node].
DPa[node] = cost of conquering subtree rooted at node assuming that the parent of the node was already conquered
DPb[node] = cost of conquering subtree rooted at node assuming that the parent of the node was not yet conquered and will be conquered after conquering this node.
For a lead node: DPa[leaf] = 0, because if its parent has been conquered then even this will be conquered.
DPb[leaf] = p[i] as the only way to conquer this would be to send troops at day 0.
For non-leaf node:
buycost of node = (sum of DPa[u] for u children of node) + p[node]
DPa[node] will be the cost of conquering P[node] - 1 children before this node and the rest after this.
We can easily calculate this with the help of a difference array between DPb and DPa. DPa[node] is the minimum between this val and the buycost.
DPb[node] will be the cost of conquering p[node] children before this node and the rest after. DPbb[node] is the minimum between this val and the buycost.
The only difference between A and B is that in A we conquer P[i] - 1 nodes while in B we conquer P[i] nodes.
Final answer is min(DPa, DPb)
This is what I came up with as well
Link to code please…