PROBLEM LINK:Author: Abhineet Shrivastava, Ishank Bhardwaj Tester: Ishank Bhardwaj Editorialist: Abhineet Shrivastava DIFFICULTY:MEDIUMHARD PREREQUISITES:Least Common Ancestor, DP, Graphs PROBLEM:Given a rooted tree with N nodes and Q queries. In each query, two nodes A and B are given. The problem is to calculate path from node A to node B using a special traversal. In the traversal from node A to node B, you can reverse your direction only once. Reversing the direction means earlier the you were going towards the root, then away from the root or vice versa. EXPLANATION:The problem can be solved using LCA and dp on trees. Preprocessing steps:
Calculation steps: Every query can be answered in O(log(n)). There are three cases.
AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. Tester's solution can be found here.
This question is marked "community wiki".
asked 27 Oct '18, 23:35
