Editorial for Pondo LCA I

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.

Approach

Root the tree at vertex $1$ ~1~ and record an Euler tour of visits: append a vertex when the search enters it, and append it again each time the search returns from a child. Also store the depth of the vertex at each tour index, and the first index at which each vertex appears.

For a query $(u, v)$ ~(u, v)~, the lowest common ancestor is the vertex of minimum depth on the tour between $\mathrm{first}[u]$ ~\mathrm{first}[u]~ and $\mathrm{first}[v]$ ~\mathrm{first}[v]~ (inclusive). The bounds are small enough to scan that range in $O(n)$ ~O(n)~ time per query, for a total of $O(n + qn)$ ~O(n + qn)~.

Solution (Python)

import sys

sys.setrecursionlimit(1_000_000)

data = list(map(int, sys.stdin.buffer.read().split()))
it = iter(data)
n = next(it)
q = next(it)
adj = [[] for _ in range(n)]
for _ in range(n - 1):
    u = next(it) - 1
    v = next(it) - 1
    adj[u].append(v)
    adj[v].append(u)

tour = []
tour_h = []
first = [-1] * n


def dfs(u, p, h):
    first[u] = len(tour)
    tour.append(u)
    tour_h.append(h)
    for v in adj[u]:
        if v == p:
            continue
        dfs(v, u, h + 1)
        tour.append(u)
        tour_h.append(h)


dfs(0, -1, 0)

out = []
for _ in range(q):
    u = next(it) - 1
    v = next(it) - 1
    l = first[u]
    r = first[v]
    if l > r:
        l, r = r, l
    best = l
    for i in range(l + 1, r + 1):
        if tour_h[i] < tour_h[best]:
            best = i
    out.append(str(tour[best] + 1))

print("\n".join(out))

Comments

There are no comments at the moment.