ANCESTOR - Editorial

Let us first construct euler tour of both the trees. Let start1[u], start2[u] denote the start time in the first tree and the second tree respectively. Similarly, we define end1[u], end2[u].

A vertex x will be ancestor of node y in both the trees iff it satisifed the follwing conditions.

  • start1[x] \leq start1[y] \leq end1[y] \leq end1[x].
  • start2[x] \leq start2[y] \leq end2[y] \leq end2[x].

Assume that we had a rectangle with bottom left point with start1[x], start2[x], and the top right with end1[x], end2[x], then you can see that the points corresponding to node y, i.e. (start1[y], start2[y]) and (end1[y], end2[y]) will lie inside the rectangle.

For a given y, we want to find number of such x's. This problem now converts into number of rectangles out of these n rectangles that contain the point y.