## 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:

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: **

## Comments