## 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 define whether node is on the path from to , and define whether node is on the path from to .

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

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

Then, we can check which nodes are on both paths by checking if both and for all .

Time Complexity: