The approach I am sharing here uses the Greedy-Algorithm and BFS for tree-traversal.
It's obvious that we'll start deleting nodes from the top. Observe that in each operation in which we delete a node, the virus would infect at most 1 more node. To save most nodes, virus propagation has to be stopped using minimum deletion operations.
The question is, when does virus propagation stop?
It stops in either of the cases:
The virus has reached a leaf node.
The virus reaches a node which has a single child (In this case, as soon as the virus reaches such a node, we'll delete it's child and then the virus will have nowhere to propagate)
So, the question essentially is to be able to find either of the above 2 types of node which is closest to the root.
The number of nodes saved in the 1st case would be n-2*l+1 and in the 2nd case, it would be n-2*l. You can verify this by taking examples. (n=number of nodes, l=level in the tree at which such a node is present.)
Also, note that if there are nodes of type-1 and type-2, minimally equidistant from the node, we'll obviously go with case-1.
Comments (0)
