PROBLEM LINK:
Editorialist: Karan Aggarwal
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
TREES
PROBLEM:
Problem : Given a tree with N root at Node 1. We receive M message, each having a node X. Message means that a kid is trapped at node X. The only way to escape from a node is to go to to its parent, till the root.
For each message, print the number of nodes that Leonardo can destroy without trapping any of the kids mentioned so far in the messages.
EXPLANATION:
Lets try to solve with problem for one message.
Lets say there is a child in node X, then we can’t destroy any node in the path from root (1) to node X.
So number of nodes we can destroy is N - (number of nodes we can’t destroy).
Now we need to find out the number of nodes we can’t destroy after each message.
Initially when no message is received, number of nodes we cannot destroy is 0.
For each message X, we start from node X, and move up till the root, and marks all the nodes in the path as destroyed.
Also, keep a counter for number of nodes destroyed till now, and increment it, if a new node is destroyed while tracing the path.
This is in worst case O(N) per message.
But the trick here is while moving up, stop as soon as you find a already destroyed node. Since, we can be sure that all the nodes above it will also be already destroyed.
Hence for a single message, one might take O(N), but overall complexity is O(N), since each node is destroyed at most once.