1 solutions
-
0thakuremon LV 4 @ 2024-12-10 19:30:59
Root the tree at any node lets say at 1.
For each query we just need to find two special node \(X,Y\) to answer the query.\(Dis\) : shortest distance of node \(C\) and \(P\)
\(X\) : the furthest node from \(C\) in the path of \(C\) to \(P\) where terrorists can reach safely before police. This node must be the node at distance \([(Dis-1)/2]\) from node \(C\).\(Y\) : the nearest node from \(C\) in the path of \(C\) to \(P\) where terrorists will be caught if they try to visit this node. This node must be the node at distance \([(Dis-1)/2]+1\). Basically this is the next node of \(X\) in the path of \(C\) to \(P\)
\(X\) and \(Y\) can be found easily using lowest common ancestor and \(k-th\) parent in \(log(N)\) time.
Now if we remove the edge between node \(X\) and \(Y\) we will have 2 separate tree lets name them \(X-tree\) and \(Y-tree\).
Terrorists can visit any node in \(X-tree\) before police but if they try to visit any node in \(Y-tree\) then they must go through \(Y\) node first and by definition of the \(Y\) node they will be get arrested in \(Y\) node.So finally we just need to check if \(X-tree\) contains at least one vulnerable node or not so that the terrorists can escape.
We can find the number of vulnerable nodes in \(X-tree\) and \(Y-tree\) using subtree sum in constant time.total complexity: \(Q*log(N)\)
- 1
Information
- ID
- 1134
- Difficulty
- 8
- Category
- (None)
- Tags
- (None)
- # Submissions
- 54
- Accepted
- 5
- Accepted Ratio
- 9%
- Uploaded By