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.