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]$ ~onPath[0][u]~ define whether node $u$ ~u~ is on the path from $a$ ~a~ to $b$ ~b~, and $onPath[1][u]$ ~onPath[1][u]~ define whether node $u$ ~u~ is on the path from $c$ ~c~ to $d$ ~d~.

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

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

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

Time Complexity: $\mathcal{O}(N)$ ~\mathcal{O}(N)~

Comments

There are no comments at the moment.