Editorial for A Tree Problem

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Ninjaclasher

Let onPath[0][u] define whether node u is on the path from a to b, and onPath[1][u] define whether node u is on the path from c to d.

We can first run a depth-first-search (DFS) starting from node a. For each child u, we can check if node b is in u's subtree (including u). If it is, this means that node u must be on the path from a to b (as there is only one path between any two nodes in a tree), and we can set onPath[0][u] = True. We can then push this information onto u's parent (marking it as True as well).

We can use the same approach for the path from node c to d.

Then, we can check which nodes are on both paths by checking if both onPath[0][i] = True and onPath[1][i] = True for all i\ (1 \le i \le N).

Time Complexity: \mathcal{O}(N)


There are no comments at the moment.