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.

Hi.

Recently, I was solving a problem from the EDU section course. After solving it, I was interested in seeing the standings for a specific list. Unfortunately, I discovered that Codeforces has a bug when working with lists in the EDU section course. I mean, try to go to the EDU section course, open the standings, and click this

The button near to word "Standings". And choose some list, and unfortunately you will see that standings remain the same(they don't show only the people who are in the list).

MikeMirzayanov, Please fix it.