test/tree/heavy_light_decomposition.lca.test.cpp

View this file on GitHub
Last update: 2025-11-15 20:52:05+09:00
Problem: https://judge.yosupo.jp/problem/lca

Depends on

Required by

test/utility/next_combination.test.cpp

Code

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

#include "../../tree/heavy_light_decomposition.hpp"
#include "../../template/template.hpp"

int main() {
    int N, Q;
    cin >> N >> Q;

    HeavyLightDecomposition hld(N);
    rep (i, 1, N) {
        int p;
        cin >> p;

        hld.add_edge(i, p);
    }

    hld.build();

    while (Q--) {
        int u, v;
        cin >> u >> v;

        cout << hld.lca(u, v) << LF;
    }

    return 0;
}

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

#line 2 "tree/heavy_light_decomposition.hpp"

#line 2 "template/template.hpp"

/**
 * @author ku_senjan
 * @title 提出用テンプレート
 * @see https://github.com/kogetsu0728/ku-library
 */

#line 2 "template/constant.hpp"

#line 2 "template/include.hpp"

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>
using namespace std;
#line 2 "template/type_alias.hpp"

#line 4 "template/type_alias.hpp"

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

using ld = long double;

template <class T, bool REVERSE = false>
using heap = priority_queue<T, vector<T>, conditional_t<REVERSE, greater<T>, less<T>>>;
#line 5 "template/constant.hpp"

template <class T>
inline constexpr T INF = numeric_limits<T>::max() / 2;

inline constexpr array<int, 4> DY4 = {0, -1, 0, 1};
inline constexpr array<int, 4> DX4 = {1, 0, -1, 0};
inline constexpr array<int, 8> DY8 = {0, -1, -1, -1, 0, 1, 1, 1};
inline constexpr array<int, 8> DX8 = {1, 1, 0, -1, -1, -1, 0, 1};

inline constexpr char LF = '\n';
#line 2 "template/macro.hpp"

#line 5 "template/macro.hpp"

/**
 * @see https://trap.jp/post/1224/
 */

#ifdef LOCAL
inline constexpr bool IS_LOCAL = true;
#else
inline constexpr bool IS_LOCAL = false;
#endif

#define IF_LOCAL if constexpr (IS_LOCAL)

#define all(a) begin(a), end(a)
#define rall(a) rbegin(a), rend(a)

#define overload4(a, b, c, d, e, ...) e

#define rep1(i, a) for (ll i = 0; (i) < (ll)(a); ++(i))
#define rep2(i, a, b) for (ll i = (ll)(a); (i) < (ll)(b); ++(i))
#define rep3(i, a, b, c) for (ll i = (ll)(a); (i) < (ll)(b); (i) += (ll)(c))
#define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)

#define rrep1(i, a) for (ll i = (ll)(a); (i) >= 0; --(i))
#define rrep2(i, a, b) for (ll i = (ll)(a); (i) >= (ll)(b); --(i))
#define rrep3(i, a, b, c) for (ll i = (ll)(a); (i) >= (ll)(b); (i) -= (ll)(c))
#define rrep(...) overload4(__VA_ARGS__, rrep3, rrep2, rrep1)(__VA_ARGS__)
#line 13 "template/template.hpp"

#line 2 "utility/choose_min_max.hpp"

/**
 * @title Choose Minimum / Maximum
 */

template <class T>
bool chmin(T& a, const T& b) {
    if (a > b) {
        a = b;
        return true;
    }

    return false;
}

template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }

    return false;
}
#line 2 "utility/set_io.hpp"

#line 4 "utility/set_io.hpp"

void set_io(int d = 16) {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(d);

    return;
}
#line 4 "tree/heavy_light_decomposition.hpp"

/**
 * @brief Heavy Light Decomposition (HL分解)
 */
class HeavyLightDecomposition {
  private:
    bool init;
    int n;
    vector<vector<int>> g;
    vector<int> siz, par, dep, top, in, out;

    void dfs_siz(int v, int p) {
        par[v] = p;

        for (int& nv : g[v]) {
            if (nv == p) {
                if (nv == g[v].back()) {
                    break;
                }

                swap(nv, g[v].back());
            }

            dfs_siz(nv, v);
            siz[v] += siz[nv];

            if (siz[nv] > siz[g[v][0]]) {
                swap(nv, g[v][0]);
            }
        }

        return;
    }

    void dfs_hld(int v, int p, int& i) {
        in[v] = i;
        i++;

        for (int& nv : g[v]) {
            if (nv == p) {
                continue;
            }

            dep[nv] = dep[v] + 1;

            if (nv == g[v][0]) {
                top[nv] = top[v];
            } else {
                top[nv] = nv;
            }

            dfs_hld(nv, v, i);
        }

        out[v] = i;

        return;
    }

  public:
    HeavyLightDecomposition() : HeavyLightDecomposition(0) {}
    HeavyLightDecomposition(int _n)
        : init(false),
          g(_n),
          siz(_n, 1),
          par(_n, -1),
          dep(_n),
          top(_n),
          in(_n),
          out(_n) {}

    void add_edge(int u, int v) {
        assert(!init);

        g[u].emplace_back(v);
        g[v].emplace_back(u);

        return;
    }

    void build() {
        assert(!init);
        init = true;

        dfs_siz(0, -1);

        int i = 0;
        dfs_hld(0, -1, i);

        return;
    }

    int depth(int v) const {
        assert(init);

        return dep[v];
    }

    int lca(int u, int v) const {
        assert(init);

        while (true) {
            if (in[u] > in[v]) {
                swap(u, v);
            }

            if (top[u] == top[v]) {
                return u;
            }

            v = par[top[v]];
        }
    }

    void node_query(int v, const function<void(int)>& func) const {
        assert(init);

        func(in[v]);

        return;
    }

    void subtree_query(int v, const function<void(int, int)>& func) const {
        assert(init);

        func(in[v], out[v]);

        return;
    }

    void path_query(int u, int v, const function<void(int, int)>& func) const {
        assert(init);

        while (true) {
            if (in[u] > in[v]) {
                swap(u, v);
            }

            func(max(in[u], in[top[v]]), in[v] + 1);

            if (top[u] == top[v]) {
                break;
            }

            v = par[top[v]];
        }

        return;
    }
};
#line 5 "test/tree/heavy_light_decomposition.lca.test.cpp"

int main() {
    int N, Q;
    cin >> N >> Q;

    HeavyLightDecomposition hld(N);
    rep (i, 1, N) {
        int p;
        cin >> p;

        hld.add_edge(i, p);
    }

    hld.build();

    while (Q--) {
        int u, v;
        cin >> u >> v;

        cout << hld.lca(u, v) << LF;
    }

    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	almost_line_00	AC	965 ms	53 MB
g++	almost_line_01	AC	1023 ms	53 MB
g++	binary_00	AC	1466 ms	42 MB
g++	binary_01	AC	1557 ms	42 MB
g++	binary_02	AC	1574 ms	42 MB
g++	example_00	AC	6 ms	3 MB
g++	line_00	AC	756 ms	51 MB
g++	line_01	AC	757 ms	60 MB
g++	line_02	AC	511 ms	10 MB
g++	line_03	AC	201 ms	55 MB
g++	line_04	AC	252 ms	37 MB
g++	max_line_00	AC	898 ms	64 MB
g++	max_line_01	AC	896 ms	64 MB
g++	max_line_02	AC	894 ms	64 MB
g++	max_random_00	AC	1355 ms	43 MB
g++	max_random_01	AC	1294 ms	43 MB
g++	max_random_02	AC	1280 ms	43 MB
g++	path_graph_root_centroid_00	AC	918 ms	53 MB
g++	path_graph_root_centroid_01	AC	889 ms	53 MB
g++	path_graph_root_centroid_02	AC	863 ms	53 MB
g++	random_00	AC	1009 ms	34 MB
g++	random_01	AC	1135 ms	40 MB
g++	random_02	AC	579 ms	7 MB
g++	random_03	AC	395 ms	37 MB
g++	random_04	AC	415 ms	25 MB