Editorial for Kinship

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

The superiors form a tree rooted at goblin $0$ ~0~. For a query $(a, b)$ ~(a, b)~, the closest shared superior is the lowest common ancestor $\mathrm{lca}(a, b)$ ~\mathrm{lca}(a, b)~.

Precompute binary lifting tables $up[v][j]$ ~up[v][j]~: the $2^j$ ~2^j~-th superior of $v$ ~v~. To answer a query, lift the deeper node up to the same depth as the shallower one. If they meet, that node is the answer. Otherwise, lift both nodes together as high as possible while their ancestors differ, then take one final step to the parent. Each query runs in $O(\log n)$ ~O(\log n)~ after $O(n \log n)$ ~O(n \log n)~ preprocessing. Overall time is $O((n + q) \log n)$ ~O((n + q) \log n)~.

Solution (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;

    vector<vector<int> > adj(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    vector<int> parent(n, -1);
    vector<int> depth(n, 0);
    stack<int> st;
    st.push(0);
    parent[0] = 0;
    while (!st.empty()) {
        int v = st.top();
        st.pop();
        for (size_t i = 0; i < adj[v].size(); i++) {
            int to = adj[v][i];
            if (parent[to] != -1) {
                continue;
            }
            parent[to] = v;
            depth[to] = depth[v] + 1;
            st.push(to);
        }
    }

    int LOGN = 1;
    while ((1 << LOGN) <= n) {
        LOGN++;
    }
    vector<vector<int> > up(n, vector<int>(LOGN));
    for (int i = 0; i < n; i++) {
        up[i][0] = parent[i];
    }
    for (int j = 1; j < LOGN; j++) {
        for (int i = 0; i < n; i++) {
            up[i][j] = up[up[i][j - 1]][j - 1];
        }
    }

    auto lift = [&](int v, int dist) {
        for (int j = 0; j < LOGN; j++) {
            if ((dist >> j) & 1) {
                v = up[v][j];
            }
        }
        return v;
    };

    auto lca = [&](int a, int b) {
        if (depth[a] < depth[b]) {
            swap(a, b);
        }
        a = lift(a, depth[a] - depth[b]);
        if (a == b) {
            return a;
        }
        for (int j = LOGN - 1; j >= 0; j--) {
            if (up[a][j] != up[b][j]) {
                a = up[a][j];
                b = up[b][j];
            }
        }
        return up[a][0];
    };

    for (int qi = 0; qi < q; qi++) {
        int a, b;
        cin >> a >> b;
        cout << lca(a, b) << "\n";
    }
}

Comments

There are no comments at the moment.