Editorial for Kinship

Use this editorial only when stuck, and do not 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$ . For a query $(a, b)$ , the closest shared superior is the lowest common ancestor $\mathrm{lca}(a, b)$ .

Precompute binary lifting tables $up[v][j]$ : the $2^j$ -th superior of $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)$ after $O(n \log n)$ preprocessing. Overall time is $O((n + q) \log n)$ .

Solution (C++)

Code 1

#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";
    }
}

Comments0

No comments yet

Be the first to comment.

Editorial for Kinship

Approach

Solution (C++)

Comments0

New comment