test/Tree/heavy_light_decomposition/yosupo-lca.cpp

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

Depends on

Heavy-Light 分解 (HLD) (Tree/heavy_light_decomposition.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/lca

#include "Tree/heavy_light_decomposition.hpp"
#include <atcoder/segtree>
#include <bits/stdc++.h>
using namespace std;

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

    HeavyLightDecomposition hld(N);

    for (int i = 0; i < N - 1; i++)
    {
        int p;
        cin >> p;
        hld.add_edge(i + 1, p);
    }

    for (int i = 0; i < Q; i++)
    {
        int u, v;
        cin >> u >> v;
        cout << hld.lca(u, v) << endl;
    }

    return 0;
}

#line 1 "test/Tree/heavy_light_decomposition/yosupo-lca.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/lca

#line 1 "Tree/heavy_light_decomposition.hpp"
#include <bits/stdc++.h>
using namespace std;

class HeavyLightDecomposition
{
public:
    HeavyLightDecomposition(int n)
        : n(n), edges(n), parent(n, -1), depth(n, 0), heavy(n, -1), head(n), pos(n), sz(n), built(false)
    {
    }

    void add_edge(int u, int v)
    {
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        edges[u].push_back(v);
        edges[v].push_back(u);
    }

    void build(int root = 0)
    {
        assert(0 <= root && root < n);
        if (built)
        {
            return;
        }

        parent[root] = -1;
        depth[root] = 0;
        dfs_size(root);

        int time = 0;
        decompose(root, root, time);
        built = true;
    }

    vector<tuple<int, int, bool>> get_path_ranges(int from, int to)
    {
        assert(0 <= from && from < n);
        assert(0 <= to && to < n);
        ensure_built();

        list<tuple<int, int, bool>> from_ranges, to_ranges;

        while (head[from] != head[to])
        {
            if (depth[head[to]] < depth[head[from]])
            {
                from_ranges.push_back({pos[head[from]], pos[from] + 1, true});
                from = parent[head[from]];
            }
            else
            {
                to_ranges.push_front({pos[head[to]], pos[to] + 1, false});
                to = parent[head[to]];
            }
        }

        if (depth[to] < depth[from])
        {
            to_ranges.push_front({pos[to], pos[from] + 1, true});
        }
        else
        {
            from_ranges.push_back({pos[from], pos[to] + 1, false});
        }

        vector<tuple<int, int, bool>> result;
        result.insert(result.end(), from_ranges.begin(), from_ranges.end());
        result.insert(result.end(), to_ranges.begin(), to_ranges.end());

        return result;
    }

    array<int, 2> get_subtree_range(int u)
    {
        assert(0 <= u && u < n);

        ensure_built();
        return {pos[u], pos[u] + sz[u]};
    }

    int lca(int u, int v)
    {
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);

        ensure_built();
        while (head[u] != head[v])
        {
            if (depth[head[u]] > depth[head[v]])
            {
                swap(u, v);
            }
            v = parent[head[v]];
        }
        return depth[u] < depth[v] ? u : v;
    }

    int get_pos(int v)
    {
        assert(0 <= v && v < n);

        ensure_built();
        return pos[v];
    }

    int get_parent(int v)
    {
        assert(0 <= v && v < n);

        ensure_built();
        return parent[v];
    }

    int get_subtree_size(int u)
    {
        assert(0 <= u && u < n);

        ensure_built();
        return sz[u];
    }

private:
    int n;
    vector<vector<int>> edges;
    vector<int> parent, depth, heavy, head, pos, sz;
    bool built;

    void ensure_built()
    {
        if (!built)
        {
            build();
        }
    }

    int dfs_size(int v)
    {
        sz[v] = 1;
        int max_size = 0;
        for (int u : edges[v])
        {
            if (u == parent[v])
            {
                continue;
            }

            parent[u] = v;
            depth[u] = depth[v] + 1;
            int sub = dfs_size(u);
            sz[v] += sub;
            if (max_size < sub)
            {
                max_size = sub;
                heavy[v] = u;
            }
        }

        return sz[v];
    }

    void decompose(int v, int h, int &time)
    {
        head[v] = h;
        pos[v] = time++;
        if (heavy[v] != -1)
        {
            decompose(heavy[v], h, time);
        }

        for (int u : edges[v])
        {
            if (u == parent[v] || u == heavy[v])
            {
                continue;
            }

            decompose(u, u, time);
        }
    }
};
#line 4 "test/Tree/heavy_light_decomposition/yosupo-lca.cpp"
#include <atcoder/segtree>
#line 6 "test/Tree/heavy_light_decomposition/yosupo-lca.cpp"
using namespace std;

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

    HeavyLightDecomposition hld(N);

    for (int i = 0; i < N - 1; i++)
    {
        int p;
        cin >> p;
        hld.add_edge(i + 1, p);
    }

    for (int i = 0; i < Q; i++)
    {
        int u, v;
        cin >> u >> v;
        cout << hld.lca(u, v) << endl;
    }

    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	almost_line_00	AC	893 ms	87 MB
g++	almost_line_01	AC	891 ms	87 MB
g++	binary_00	AC	1067 ms	42 MB
g++	binary_01	AC	1151 ms	42 MB
g++	binary_02	AC	1098 ms	42 MB
g++	example_00	AC	5 ms	3 MB
g++	line_00	AC	752 ms	104 MB
g++	line_01	AC	760 ms	123 MB
g++	line_02	AC	507 ms	17 MB
g++	line_03	AC	245 ms	114 MB
g++	line_04	AC	290 ms	75 MB
g++	max_line_00	AC	895 ms	132 MB
g++	max_line_01	AC	896 ms	132 MB
g++	max_line_02	AC	907 ms	132 MB
g++	max_random_00	AC	1028 ms	43 MB
g++	max_random_01	AC	1010 ms	43 MB
g++	max_random_02	AC	1047 ms	43 MB
g++	path_graph_root_centroid_00	AC	881 ms	87 MB
g++	path_graph_root_centroid_01	AC	853 ms	87 MB
g++	path_graph_root_centroid_02	AC	879 ms	87 MB
g++	random_00	AC	773 ms	34 MB
g++	random_01	AC	848 ms	40 MB
g++	random_02	AC	547 ms	7 MB
g++	random_03	AC	246 ms	37 MB
g++	random_04	AC	300 ms	25 MB