test/LCA.test.cpp

View this file on GitHub
Last update: 2025-07-04 15:57:54+09:00
Problem: https://judge.yosupo.jp/problem/lca

Depends on

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/lca
#include "../LCA.cpp"
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    vector<vector<int>> g(n);
    for (int i = 1; i < n; i++) {
        int p;
        cin >> p;
        g[p].push_back(i);
    }
    lca_tree lt(g);
    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << lt.lca(u, v) << "\n";
    }
}

#line 1 "test/LCA.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/lca
#line 1 "LCA.cpp"
#include <bits/stdc++.h>
#line 2 "SparseTable.cpp"
using namespace std;
template <class T, T (*op)(T, T), T (*e)()>
struct sparsetable {
    vector<vector<T>> table;
    vector<int> logtable;
    sparsetable() = default;
    sparsetable(vector<T> v) {
        int len = 0;
        while ((1 << len) <= (int)v.size()) len++;
        table.assign(len, vector<T>(1 << len));
        for (int i = 0; i < (int)v.size(); i++) table[0][i] = v[i];
        for (int i = 1; i < len; i++) {
            for (int j = 0; j + (1 << i) <= (1 << len); j++) {
                table[i][j] = op(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
            }
        }
        logtable.resize((int)v.size() + 1);
        for (int i = 2; i < (int)logtable.size(); i++) {
            logtable[i] = logtable[(i >> 1)] + 1;
        }
    }
    T query(int l, int r) {
        assert(l <= r);
        if (l == r) return e();
        int len = logtable[r - l];
        return op(table[len][l], table[len][r - (1 << len)]);
    }
};
template <class T, T (*op)(T, T), T (*e)()>
struct disjointsparsetable {
    vector<vector<T>> table;
    vector<int> logtable;
    disjointsparsetable() = default;
    disjointsparsetable(vector<T> v) {
        int len = 0;
        while ((1 << len) <= v.size()) len++;
        table.assign(len, vector<T>(1 << len, e()));
        for (int i = 0; i < (int)v.size(); i++) table[0][i] = v[i];
        for (int i = 1; i < len; i++) {
            int shift = 1 << i;
            for (int j = 0; j < (int)v.size(); j += shift << 1) {
                int t = min(j + shift, (int)v.size());
                table[i][t - 1] = v[t - 1];
                for (int k = t - 2; k >= j; k--) table[i][k] = op(v[k], table[i][k + 1]);
                if (v.size() <= t) break;
                table[i][t] = v[t];
                int r = min(t + shift, (int)v.size());
                for (int k = t + 1; k < r; k++) table[i][k] = op(table[i][k - 1], v[k]);
            }
        }
        logtable.resize(1 << len);
        for (int i = 2; i < logtable.size(); i++) {
            logtable[i] = logtable[(i >> 1)] + 1;
        }
    }
    T query(int l, int r) {
        if (l == r) return e();
        if (l >= --r) return table[0][l];
        int len = logtable[l ^ r];
        return op(table[len][l], table[len][r]);
    };
};
#line 3 "LCA.cpp"
using namespace std;
pair<int, int> lcatree_op(pair<int, int> a, pair<int, int> b) { return min(a, b); }
pair<int, int> lcatree_e() { return {1000000000, -1}; }
struct lca_tree {
    int n, size;
    vector<int> in, ord, depth;
    disjointsparsetable<pair<int, int>, lcatree_op, lcatree_e> st;
    lca_tree(vector<vector<int>> g, int root = 0) : n((int)g.size()), size(log2(n) + 2), in(n), depth(n, n) {
        depth[root] = 0;
        function<void(int, int)> dfs = [&](int v, int p) {
            in[v] = (int)ord.size();
            ord.push_back(v);
            for (int u : g[v]) {
                if (u == p) continue;
                if (depth[u] > depth[v] + 1) {
                    depth[u] = depth[v] + 1;
                    dfs(u, v);
                    ord.push_back(v);
                }
            }
        };
        dfs(root, -1);
        vector<pair<int, int>> vec((int)ord.size());
        for (int i = 0; i < (int)ord.size(); i++) {
            vec[i] = make_pair(depth[ord[i]], ord[i]);
        }
        st = vec;
    }
    int lca(int u, int v) {
        if (in[u] > in[v]) swap(u, v);
        if (u == v) return u;
        return st.query(in[u], in[v]).second;
    }
    int dist(int u, int v) {
        int l = lca(u, v);
        return depth[u] + depth[v] - 2 * depth[l];
    }
};
#line 3 "test/LCA.test.cpp"
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    vector<vector<int>> g(n);
    for (int i = 1; i < n; i++) {
        int p;
        cin >> p;
        g[p].push_back(i);
    }
    lca_tree lt(g);
    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << lt.lca(u, v) << "\n";
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	almost_line_00	AC	449 ms	269 MB
g++	almost_line_01	AC	434 ms	269 MB
g++	binary_00	AC	448 ms	238 MB
g++	binary_01	AC	465 ms	238 MB
g++	binary_02	AC	477 ms	238 MB
g++	example_00	AC	5 ms	4 MB
g++	line_00	AC	347 ms	279 MB
g++	line_01	AC	383 ms	299 MB
g++	line_02	AC	114 ms	36 MB
g++	line_03	AC	262 ms	290 MB
g++	line_04	AC	206 ms	250 MB
g++	max_line_00	AC	407 ms	308 MB
g++	max_line_01	AC	431 ms	308 MB
g++	max_line_02	AC	446 ms	308 MB
g++	max_random_00	AC	459 ms	238 MB
g++	max_random_01	AC	473 ms	238 MB
g++	max_random_02	AC	474 ms	238 MB
g++	path_graph_root_centroid_00	AC	371 ms	281 MB
g++	path_graph_root_centroid_01	AC	373 ms	281 MB
g++	path_graph_root_centroid_02	AC	374 ms	281 MB
g++	random_00	AC	387 ms	225 MB
g++	random_01	AC	440 ms	234 MB
g++	random_02	AC	118 ms	29 MB
g++	random_03	AC	298 ms	230 MB
g++	random_04	AC	208 ms	212 MB
clang++	almost_line_00	AC	425 ms	266 MB
clang++	almost_line_01	AC	420 ms	265 MB
clang++	binary_00	AC	470 ms	238 MB
clang++	binary_01	AC	460 ms	238 MB
clang++	binary_02	AC	448 ms	238 MB
clang++	example_00	AC	5 ms	4 MB
clang++	line_00	AC	334 ms	273 MB
clang++	line_01	AC	369 ms	291 MB
clang++	line_02	AC	112 ms	35 MB
clang++	line_03	AC	249 ms	284 MB
clang++	line_04	AC	197 ms	246 MB
clang++	max_line_00	AC	402 ms	301 MB
clang++	max_line_01	AC	393 ms	301 MB
clang++	max_line_02	AC	409 ms	301 MB
clang++	max_random_00	AC	482 ms	238 MB
clang++	max_random_01	AC	471 ms	238 MB
clang++	max_random_02	AC	462 ms	238 MB
clang++	path_graph_root_centroid_00	AC	356 ms	277 MB
clang++	path_graph_root_centroid_01	AC	360 ms	277 MB
clang++	path_graph_root_centroid_02	AC	365 ms	277 MB
clang++	random_00	AC	361 ms	225 MB
clang++	random_01	AC	400 ms	234 MB
clang++	random_02	AC	114 ms	29 MB
clang++	random_03	AC	271 ms	230 MB
clang++	random_04	AC	203 ms	211 MB