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)$$

Comments

There are no comments at the moment.