test/lca.test.cpp

• View this file on GitHub
• Last update: 2025-05-28 17:58:43+09:00
• Problem: https://judge.yosupo.jp/problem/lca

Depends on

• Link-Cut Tree (data_structure/link_cut_tree.hpp)
• data_structure/splay_tree.hpp

Code

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

#include <data_structure/link_cut_tree.hpp>  // for StrongLinkCutTree
#include <fastio/base.hpp>                          // for FASTIO, cin, cout
#include <fastio/char/write.hpp>                    // for operator<<
#include <fastio/signed/read.hpp>                   // for operator>>
#include <fastio/signed/write.hpp>                  // for operator<<
#include <format>                                   // for vector
#include <templates/macro/abbrev/eb.hpp>            // for eb
#include <templates/macro/abbrev/endl.hpp>          // for endl
#include <templates/macro/segtree/RSQ.hpp>          // for RSQ
#include <templates/rep.hpp>                        // for rep
#include <templates/template.hpp>
#include <vector>                                   // for vector

int main() {
    int n, q;
    cin >> n >> q;
    vector<vector<int>> g(n);
    rep(i, 1, n) {
        int u;
        cin >> u;
        g[u].eb(i);
    }
    LinkCutTree<RSQ(int, 0)> lct(g);
    rep(_, q) {
        int u, v;
        cin >> u >> v;
        cout << lct.lca(u, v) << endl;
    }
}

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

#include <data_structure/link_cut_tree.hpp>  // for StrongLinkCutTree
#include <fastio/base.hpp>                          // for FASTIO, cin, cout
#include <fastio/char/write.hpp>                    // for operator<<
#include <fastio/signed/read.hpp>                   // for operator>>
#include <fastio/signed/write.hpp>                  // for operator<<
#include <format>                                   // for vector
#include <templates/macro/abbrev/eb.hpp>            // for eb
#include <templates/macro/abbrev/endl.hpp>          // for endl
#include <templates/macro/segtree/RSQ.hpp>          // for RSQ
#include <templates/rep.hpp>                        // for rep
#include <templates/template.hpp>
#include <vector>                                   // for vector

int main() {
    int n, q;
    cin >> n >> q;
    vector<vector<int>> g(n);
    rep(i, 1, n) {
        int u;
        cin >> u;
        g[u].eb(i);
    }
    LinkCutTree<RSQ(int, 0)> lct(g);
    rep(_, q) {
        int u, v;
        cin >> u >> v;
        cout << lct.lca(u, v) << endl;
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	almost_line_00	AC	1186 ms	73 MB
g++	almost_line_01	AC	1178 ms	73 MB
g++	binary_00	AC	1578 ms	71 MB
g++	binary_01	AC	1585 ms	71 MB
g++	binary_02	AC	1597 ms	71 MB
g++	example_00	AC	5 ms	4 MB
g++	line_00	AC	940 ms	64 MB
g++	line_01	AC	994 ms	73 MB
g++	line_02	AC	596 ms	18 MB
g++	line_03	AC	189 ms	64 MB
g++	line_04	AC	269 ms	44 MB
g++	max_line_00	AC	1220 ms	79 MB
g++	max_line_01	AC	1242 ms	79 MB
g++	max_line_02	AC	1222 ms	79 MB
g++	max_random_00	AC	1131 ms	71 MB
g++	max_random_01	AC	1153 ms	71 MB
g++	max_random_02	AC	1133 ms	71 MB
g++	path_graph_root_centroid_00	AC	1244 ms	79 MB
g++	path_graph_root_centroid_01	AC	1231 ms	79 MB
g++	path_graph_root_centroid_02	AC	1239 ms	79 MB
g++	random_00	AC	881 ms	57 MB
g++	random_01	AC	944 ms	65 MB
g++	random_02	AC	568 ms	17 MB
g++	random_03	AC	197 ms	57 MB
g++	random_04	AC	266 ms	40 MB

Back to top page