test/yosupo/tree/lca_hld.test.cpp

• View this file on GitHub
• Last update: 2025-09-25 11:45:13+07:00
• Problem: https://judge.yosupo.jp/problem/lca

Depends on

• Compressed Sparse Row (graph/csr.hpp)
• Heavy-light Decomposition (tree/hld.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/lca"

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

#include "graph/csr.hpp"
#include "tree/hld.hpp"

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    vector<pair<int, int>> es(n - 1);
    for (int i = 1; i < n; i++) {
        int p;
        cin >> p;
        es[i - 1] = {p, i};
    }
    CSR<int> g(n, move(es));
    HLD hld(g);
    while (q--) {
        int u, v;
        cin >> u >> v, cout << hld.lca(u, v) << "\n";
    }
}

#line 1 "test/yosupo/tree/lca_hld.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/lca"

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

#line 2 "graph/csr.hpp"

template<class E> struct CSR {
    CSR() {}
    CSR(int _n, const vector<pair<int, E>> &_edges) :
        n(_n), start(n + 1), edges((int)_edges.size()) {
        for (auto &[from, _] : _edges) start[from + 1]++;
        for (int i = 1; i <= n; i++) start[i] += start[i - 1];
        auto cnt = start;
        for (auto &[from, e] : _edges) edges[cnt[from]++] = e;
    }

    int size() const { return n; }

    struct range {
        E *edges;
        const int first, last;
        struct iterator {
            E *elist;
            int p;
            bool operator!=(const iterator &r) const { return p != r.p; }
            void operator++() { p++; }
            E &operator*() { return elist[p]; }
        };
        E &operator[](size_t i) {
            assert(i < size());
            return edges[first + i];
        }
        E &back() { return edges[last - 1]; }
        iterator begin() { return {edges, first}; }
        iterator end() { return {edges, last}; }
        int size() const { return last - first; }
        bool empty() const { return first == last; }
    };
    struct const_range {
        const E *edges;
        const int first, last;
        struct iterator {
            const E *elist;
            int p;
            bool operator!=(const iterator &r) const { return p != r.p; }
            void operator++() { p++; }
            const E &operator*() const { return elist[p]; }
        };
        const E &operator[](size_t i) const {
            assert(i < size());
            return edges[first + i];
        }
        const E &back() const { return edges[last - 1]; }
        iterator begin() const { return {edges, first}; }
        iterator end() const { return {edges, last}; }
        int size() const { return last - first; }
        bool empty() const { return first == last; }
    };
    range operator[](size_t i) {
        assert(i < size());
        return {edges.data(), start[i], start[i + 1]};
    }
    const_range operator[](size_t i) const {
        assert(i < size());
        return {edges.data(), start[i], start[i + 1]};
    }

    struct iterator {
        CSR *g;
        int p;
        bool operator!=(const iterator &r) const { return p != r.p; }
        void operator++() { p++; }
        range operator*() { return (*g)[p]; }
    };
    struct const_iterator {
        const CSR *g;
        int p;
        bool operator!=(const const_iterator &r) const { return p != r.p; }
        void operator++() { p++; }
        const_range operator*() const { return (*g)[p]; }
    };
    iterator begin() { return {this, 0}; }
    iterator end() { return {this, n}; }
    const_iterator begin() const { return {this, 0}; }
    const_iterator end() const { return {this, n}; }

  private:
    int n;
    vector<int> start;
    vector<E> edges;
};
#line 2 "tree/hld.hpp"

struct HLD {
    int n;
    vector<int> in, par, dep, out, hs;

    template<class G>
    HLD(G &g, int root = 0) :
        n((int)g.size()), in(n), par(n), dep(n), out(n), hs(n) {
        hs[root] = root;
        dfs_sz(g, root);
        dfs_hld(g, root);
        assert(time == n);
    }

    int lca(int u, int v) const {
        assert(0 <= u && u < n && 0 <= v && v < n);
        for (;; v = par[hs[v]]) {
            if (in[u] > in[v]) swap(u, v);
            if (hs[u] == hs[v]) return u;
        }
    }
    int dist(int u, int v) const {
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }
    auto path(int v, int p, bool es = 0) const {
        assert(in[p] <= in[v] && out[v] <= out[p]);
        vector<pair<int, int>> res;
        for (; hs[v] != hs[p]; v = par[hs[v]])
            res.emplace_back(in[hs[v]], in[v] + 1);
        res.emplace_back(in[p] + es, in[v] + 1);
        return res;
    }
    pair<int, int> subtree(int v) const {
        assert(0 <= v && v < n);
        return {in[v], out[v]};
    }
    int operator[](int v) { return in[v]; }
    int operator()(int v) { return out[v]; }

  private:
    int time = 0;
    template<class G> int dfs_sz(G &g, int v, int p = -1) {
        par[v] = p;
        int sz = 1, mx = 0;
        for (auto &c : g[v]) {
            if (c == p) continue;
            dep[c] = dep[v] + 1;
            int s = dfs_sz(g, c, v);
            sz += s;
            if (g[v][0] == p || mx < s) mx = s, swap(g[v][0], c);
        }
        return sz;
    }
    template<class G> void dfs_hld(G &g, int v, int p = -1) {
        in[v] = time++;
        for (auto c : g[v]) {
            if (c == p) continue;
            hs[c] = (c == g[v][0] ? hs[v] : c);
            dfs_hld(g, c, v);
        }
        out[v] = time;
    }
};
#line 8 "test/yosupo/tree/lca_hld.test.cpp"

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    vector<pair<int, int>> es(n - 1);
    for (int i = 1; i < n; i++) {
        int p;
        cin >> p;
        es[i - 1] = {p, i};
    }
    CSR<int> g(n, move(es));
    HLD hld(g);
    while (q--) {
        int u, v;
        cin >> u >> v, cout << hld.lca(u, v) << "\n";
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	almost_line_00	AC	182 ms	48 MB
g++	almost_line_01	AC	198 ms	48 MB
g++	binary_00	AC	275 ms	21 MB
g++	binary_01	AC	280 ms	21 MB
g++	binary_02	AC	267 ms	21 MB
g++	example_00	AC	5 ms	4 MB
g++	line_00	AC	150 ms	60 MB
g++	line_01	AC	164 ms	70 MB
g++	line_02	AC	74 ms	11 MB
g++	line_03	AC	91 ms	65 MB
g++	line_04	AC	74 ms	43 MB
g++	max_line_00	AC	187 ms	76 MB
g++	max_line_01	AC	180 ms	76 MB
g++	max_line_02	AC	188 ms	76 MB
g++	max_random_00	AC	207 ms	21 MB
g++	max_random_01	AC	203 ms	21 MB
g++	max_random_02	AC	205 ms	21 MB
g++	path_graph_root_centroid_00	AC	155 ms	48 MB
g++	path_graph_root_centroid_01	AC	155 ms	48 MB
g++	path_graph_root_centroid_02	AC	154 ms	48 MB
g++	random_00	AC	165 ms	17 MB
g++	random_01	AC	176 ms	20 MB
g++	random_02	AC	92 ms	5 MB
g++	random_03	AC	67 ms	18 MB
g++	random_04	AC	65 ms	13 MB
clang++	almost_line_00	AC	198 ms	40 MB
clang++	almost_line_01	AC	196 ms	40 MB
clang++	binary_00	AC	464 ms	21 MB
clang++	binary_01	AC	456 ms	21 MB
clang++	binary_02	AC	454 ms	21 MB
clang++	example_00	AC	5 ms	4 MB
clang++	line_00	AC	151 ms	48 MB
clang++	line_01	AC	162 ms	56 MB
clang++	line_02	AC	74 ms	9 MB
clang++	line_03	AC	84 ms	52 MB
clang++	line_04	AC	69 ms	35 MB
clang++	max_line_00	AC	177 ms	60 MB
clang++	max_line_01	AC	180 ms	60 MB
clang++	max_line_02	AC	181 ms	60 MB
clang++	max_random_00	AC	279 ms	21 MB
clang++	max_random_01	AC	266 ms	21 MB
clang++	max_random_02	AC	263 ms	21 MB
clang++	path_graph_root_centroid_00	AC	161 ms	40 MB
clang++	path_graph_root_centroid_01	AC	165 ms	40 MB
clang++	path_graph_root_centroid_02	AC	167 ms	40 MB
clang++	random_00	AC	213 ms	17 MB
clang++	random_01	AC	243 ms	20 MB
clang++	random_02	AC	111 ms	5 MB
clang++	random_03	AC	75 ms	18 MB
clang++	random_04	AC	75 ms	13 MB

Back to top page