## Editorial for A Tree Problem

**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 \(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