Hi, everyone!

Today I want to present my novel idea of finding $$$LCA$$$ of two nodes in at most $$$O(N + \sum_{j=1}^{Q} \log_2(\max(\text{depth}_{u_j}, \text{depth}_{v_j}) + 1))$$$ in offline. As we can see, algorithm depends heavily on the depth of queries, so in random trees it might work faster and memory is also pure $$$O(N + Q)$$$.

Prerequisites

• Euler tour technique
• Basic binary search
• Understanding tree

From the time complexity and prerequisites you might have guessed that we use ancestors of nodes, it is correct! Using properties of DFS we can keep ancestors sorted by depth in $$$O(N)$$$, example pseudocode:

dfs(v):
   ancestors.add(v)
   for u in a[v]: dfs(u)
   ancestors.pop()

This is true because the moment we finished the subtree of $$$v$$$ node, we no longer can have it as a ancestor for other nodes. Since it is always sorted by depth, which is what we need for our binary search. Our task transforms into finding right-most node in our ancestors, which is ancestor of both $$$u$$$ and $$$v$$$. However we don't need out-order to check, because if current query's node partner was already visited in our DFS, then we can find LCA using only in-order.

#include <bits/stdc++.h>

using namespace std;

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, q, tim = 0;
    cin >> n >> q;
    vector<vector<int>> a(n);
    for (int i = 1; i < n; i++) {
        int p;
        cin >> p, --p, a[p].emplace_back(i);
    }
    vector<vector<pair<int, int>>> Q(n);
    for (int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y, --x, --y;
        Q[x].emplace_back(y, i);
        Q[y].emplace_back(x, i);
    }
    vector<int> st, tin(n), ans(q);
    auto lca = [&] (int x, int y) {
        int l = 0, r = st.size() - 1, top = -1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (tin[st[mid]] <= tin[x] && tin[st[mid]] <= tin[y]) l = mid + 1, top = st[mid];
            else r = mid - 1;
        }
        return top;
    };
    auto dfs = [&] (auto &dfs, int v) -> void {
        tin[v] = tim++;
        st.emplace_back(v);
        for (auto [u, i] : Q[v]) if (tin[u]) ans[i] = lca(u, v);
        for (int u : a[v]) dfs(dfs, u);
        st.pop_back();
    };
    dfs(dfs, 0);
    for (int i : ans) cout << i + 1 << '\n';
    return 0;                    
}

Verified code on a problem: https://cses.fi/problemset/task/1688/

Thanks for reading, I hope you have a nice day.