uniolympiads English

Ελάχιστος κοινός πρόγονος (binary lifting)

Ο 2k2^k-οστός πρόγονος κάθε κορυφής σε πίνακα. Με αυτόν, kk-οστός πρόγονος, LCA και απόσταση σε δέντρο, σε O(log⁡n)O(\log n) το καθένα.

Πότε

Ερωτήματα σε δέντρο: «ποιος είναι ο kk-οστός προϊστάμενος του vv;», «ποιος είναι ο κοινός προϊστάμενος των aa και bb;», «πόσες ακμές απέχουν το aa και το bb;».

Η ιδέα

up0[v]\mathrm{up}_0[v] είναι ο γονέας του vv, και upk[v]=upk−1[upk−1[v]]\mathrm{up}_k[v] = \mathrm{up}_{k-1}[\mathrm{up}_{k-1}[v]]: δύο άλματα των 2k−12^{k-1} κάνουν ένα των 2k2^k. Η ρίζα είναι πρόγονος του εαυτού της, οπότε τα άλματα που βγαίνουν από το δέντρο σταματούν εκεί.

  • kk-οστός πρόγονος: γράψε το kk στο δυαδικό και κάνε ένα άλμα για κάθε bit που είναι 1.
  • LCA: φέρε πρώτα τα aa και bb στο ίδιο βάθος. Αν συμπέσουν, τελείωσες. Αλλιώς, από το μεγαλύτερο kk προς το μικρότερο, πήδα με τα δύο μαζί όσο οι πρόγονοί τους διαφέρουν. Στο τέλος είναι παιδιά του LCA.
  • Απόσταση: depth(a)+depth(b)−2 depth(lca(a,b))\mathrm{depth}(a) + \mathrm{depth}(b) - 2\,\mathrm{depth}(\mathrm{lca}(a, b)).

Τα βάθη και οι γονείς έρχονται από BFS, όχι από αναδρομική DFS. Στο Company Queries το δέντρο μπορεί να είναι αλυσίδα μήκους 2⋅1052 \cdot 10^5.

Παγίδες

  • Η κίνηση «όσο διαφέρουν» είναι όλη η ουσία. Αν πηδάς όσο είναι ίσοι, θα ξεπεράσεις το LCA και θα φτάσεις στη ρίζα.
  • Στο Company Queries I ο kk-οστός προϊστάμενος μπορεί να μην υπάρχει (απάντηση −1-1). Έλεγξε k>depth(v)k > \mathrm{depth}(v) πριν από τα άλματα, γιατί ο κώδικας εδώ σταματά σιωπηλά στη ρίζα.

Κώδικας

Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.

cpp/lca.cpp
// Lowest common ancestor with binary lifting. Build O(n log n), query O(log n).
// up[k][v] = the 2^k-th ancestor of v (the root is its own ancestor).
// The tree is given as an adjacency list; depths come from an iterative BFS.

struct LCA {
    int n;
    int LOG;
    vector<vector<int>> up;
    vector<int> depth;

    LCA(const vector<vector<int>>& adj, int root) : n(adj.size()), depth(adj.size(), -1) {
        LOG = 1;
        while ((1 << LOG) < n) {
            LOG++;
        }
        up.assign(LOG + 1, vector<int>(n, root));
        queue<int> q;
        depth[root] = 0;
        q.push(root);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : adj[u]) {
                if (depth[v] == -1) {
                    depth[v] = depth[u] + 1;
                    up[0][v] = u;
                    q.push(v);
                }
            }
        }
        for (int k = 1; k <= LOG; k++) {
            for (int v = 0; v < n; v++) {
                up[k][v] = up[k - 1][up[k - 1][v]];
            }
        }
    }

    int kthAncestor(int v, int k) {
        for (int j = 0; j <= LOG; j++) {
            if ((k >> j) & 1) {
                v = up[j][v];
            }
        }
        return v;
    }

    int lca(int a, int b) {
        if (depth[a] < depth[b]) {
            swap(a, b);
        }
        a = kthAncestor(a, depth[a] - depth[b]);
        if (a == b) {
            return a;
        }
        for (int k = LOG; k >= 0; k--) {
            if (up[k][a] != up[k][b]) {
                a = up[k][a];
                b = up[k][b];
            }
        }
        return up[0][a];
    }

    int distance(int a, int b) {
        return depth[a] + depth[b] - 2 * depth[lca(a, b)];
    }
};

Ελέγχθηκε σε 500 τυχαίες περιπτώσεις απέναντι σε αργή, προφανώς σωστή λύση, με AddressSanitizer και UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Για εξάσκηση στο CSES

Με τη σειρά: το πρώτο είναι η καθαρή εφαρμογή, τα επόμενα θέλουν μια παραλλαγή.

Περισσότερα στο USACO Guide

Στα αγγλικά, με επιπλέον προβλήματα ανά επίπεδο.