verify/graph/tree_lca.test.cpp

View this file on GitHub
Last update: 2026-07-26 23:08:04-04:00
Problem: https://judge.yosupo.jp/problem/lca

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/lca"
#include "algo/common.h"

/* #include */
#include "algo/graph/lca.h"

using namespace std;
using namespace algo;
using graph::lca;

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> p(n);
    vector<vector<int>> adj(n);
    for (int i = 1; i < n; i++) {
        cin >> p[i];
        adj[i].push_back(p[i]);
        adj[p[i]].push_back(i);
    }
    lca lca(adj);
    for (int i = 0; i < q; i++) {
        int u, v;
        cin >> u >> v;
        cout << lca.par(u, v) << '\n';
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    // int t;
    // cin >> t;
    // while (t--)
    solve();
}

#line 1 "verify/graph/tree_lca.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/lca"
#line 2 "algo/common.h"
#ifndef PREPROCESS
#include <bits/stdc++.h>
#include <cassert>
#endif

namespace algo {

// Indices and sizes into library containers. Signed, so the usual "walk down to
// -1" loops still terminate; widening the whole library is a change here alone.
using index_t = int;

} // namespace algo
#line 3 "verify/graph/tree_lca.test.cpp"

/* #include */
#line 3 "algo/utils/bits.h"

namespace algo::utils {

// Returns number of set bits in x
constexpr int popcnt(int64_t x) {
    return __builtin_popcountll(x);
}
// Returns floor(log_2(x))
constexpr int lg2(uint64_t x) {
    return std::bit_width(x) - 1;
}

} // namespace algo::utils
#line 4 "algo/ds/sparse_table.h"

namespace algo::ds {

// An op has to be a type here, and std::min and std::max name overload sets
// rather than single functions, so wrap them.
template <typename T>
struct min_op {
    T operator()(T a, T b) const {
        return std::min(a, b);
    }
};

template <typename T>
struct max_op {
    T operator()(T a, T b) const {
        return std::max(a, b);
    }
};

template <typename T, typename Op = min_op<T>>
struct sparse_table {
    // Must be constructed with idempotent function. Call init() after if using
    // this constructor.
    sparse_table(index_t _n, Op op = Op())
        : n(_n), k(utils::lg2(n)), op(op),
          st(std::max<index_t>(k + 1, 1), std::vector<T>(n)) {
    }
    // Must be constructed with idempotent function
    sparse_table(const std::vector<T> &a, Op op = Op())
        : sparse_table((index_t)a.size(), op) {
        init(a);
    }
    void init(const std::vector<T> &a) {
        assert((index_t)a.size() <= n);
        std::copy(a.begin(), a.end(), st[0].begin());
        for (index_t i = 1; i <= k; i++) {
            for (index_t j = 0; j + (index_t(1) << i) <= n; j++) {
                st[i][j] =
                    op(st[i - 1][j], st[i - 1][j + (index_t(1) << (i - 1))]);
            }
        }
    }
    // Queries on [l, r]
    T query(index_t l, index_t r) {
        index_t i = utils::lg2(r - l + 1);
        return op(st[i][l], st[i][r - (index_t(1) << i) + 1]);
    }
    friend std::ostream &operator<<(std::ostream &os, const sparse_table &t) {
        return os << t.st[0];
    }

private:
    // k is the max level index and is -1 when n is 0, so the row count is
    // floored at 1 to keep level 0 present for init() to copy into.
    index_t n, k;
    Op op;
    std::vector<std::vector<T>> st;
};

} // namespace algo::ds
#line 5 "algo/graph/lca.h"

namespace algo::graph {

struct lca {
    // Note that adj must be a tree. Don't forget to set root!
    lca(const std::vector<std::vector<index_t>> &adj, index_t root = 0)
        : n((index_t)adj.size()), height(n), first(n), st(2 * n, {&height}) {
        euler.reserve(2 * n);
        dfs(root, root, 0, adj);
        st.init(euler);
    }
    // Lowest common ancestor of u, v
    index_t par(index_t u, index_t v) {
        index_t l = first[u], r = first[v];
        if (l > r) std::swap(l, r);
        return st.query(l, r);
    }

private:
    // The table is built before dfs fills height, so the op has to read it
    // where it lives rather than close over a copy.
    struct by_height {
        const std::vector<index_t> *height;
        index_t operator()(index_t a, index_t b) const {
            return (*height)[a] < (*height)[b] ? a : b;
        }
    };

    index_t n;
    std::vector<index_t> height, euler, first;
    ds::sparse_table<index_t, by_height> st;

    void dfs(index_t v, index_t p, index_t h,
             const std::vector<std::vector<index_t>> &adj) {
        height[v] = h;
        first[v] = (index_t)euler.size();
        euler.push_back(v);
        for (index_t u : adj[v]) {
            if (u != p) {
                dfs(u, v, h + 1, adj);
                euler.push_back(v);
            }
        }
    }
};

}; // namespace algo::graph
#line 6 "verify/graph/tree_lca.test.cpp"

using namespace std;
using namespace algo;
using graph::lca;

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> p(n);
    vector<vector<int>> adj(n);
    for (int i = 1; i < n; i++) {
        cin >> p[i];
        adj[i].push_back(p[i]);
        adj[p[i]].push_back(i);
    }
    lca lca(adj);
    for (int i = 0; i < q; i++) {
        int u, v;
        cin >> u >> v;
        cout << lca.par(u, v) << '\n';
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    // int t;
    // cin >> t;
    // while (t--)
    solve();
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	almost_line_00	AC	285 ms	142 MB
g++	almost_line_01	AC	277 ms	142 MB
g++	binary_00	AC	324 ms	119 MB
g++	binary_01	AC	323 ms	119 MB
g++	binary_02	AC	301 ms	119 MB
g++	example_00	AC	2 ms	4 MB
g++	line_00	AC	219 ms	130 MB
g++	line_01	AC	232 ms	153 MB
g++	line_02	AC	90 ms	20 MB
g++	line_03	AC	137 ms	143 MB
g++	line_04	AC	115 ms	93 MB
g++	max_line_00	AC	259 ms	166 MB
g++	max_line_01	AC	272 ms	166 MB
g++	max_line_02	AC	264 ms	165 MB
g++	max_random_00	AC	331 ms	119 MB
g++	max_random_01	AC	330 ms	119 MB
g++	max_random_02	AC	361 ms	119 MB
g++	path_graph_root_centroid_00	AC	227 ms	142 MB
g++	path_graph_root_centroid_01	AC	234 ms	142 MB
g++	path_graph_root_centroid_02	AC	230 ms	142 MB
g++	random_00	AC	263 ms	94 MB
g++	random_01	AC	322 ms	111 MB
g++	random_02	AC	85 ms	15 MB
g++	random_03	AC	174 ms	103 MB
g++	random_04	AC	135 ms	68 MB