src/alfred/graph/lca.hpp

• View this file on GitHub
• Last update: 2025-03-22 22:16:15+08:00
• Include: #include "src/alfred/graph/lca.hpp"

Depends on

• src/alfred/data_structure/sparse-table.hpp

Verified with

• verify/verify-aizu-graph/aizu-lca.test.cpp

Code

#ifndef AFGR_LCA
#define AFGR_LCA

#include "../data_structure/sparse-table.hpp"
#include <vector>

// requires a previous graph definition.
class LCAImpl {
private:
    std::vector<int> dfn, seq; // dfn and seq are (internally) zero indexed.
    static std::vector<int> d;
    struct EulerTourInfo {
        int val;
        EulerTourInfo(void) : val(0) {}
        EulerTourInfo(int x) : val(x) {}
        EulerTourInfo operator+(EulerTourInfo &x) {
            return d[val] < d[x.val] ? val : x.val;
        }
    };
    SparseTable<EulerTourInfo> lca; // 0 indexed.
    inline void _dfs(int x, int fa) {
        dfn[x] = seq.size();
        seq.push_back(x), d[x] = d[fa] + 1;
        for (auto &y : G[x]) {
            if (y == fa) continue;
            _dfs(y, x), seq.push_back(x);
        }
    }

public:
    inline void init(int n, int rt = 1) {
        d.assign(n + 1, 0), dfn.assign(n + 1, 0);
        seq.clear(), _dfs(rt, 0), lca.init(seq);
    }
    inline int LCA(int u, int v) {
        if (u == -1) return v;
        if (v == -1) return u;
        if (dfn[u] > dfn[v]) std::swap(u, v);
        return lca.query(dfn[u], dfn[v]).val;
    }
    inline int dis(int u, int v) {
        return d[u] + d[v] - 2 * d[LCA(u, v)];
    }
} LCA;
std::vector<int> LCAImpl::d;

struct LCAInfo {
    int val;
    LCAInfo(void) : val(-1) {}
    template <class InitT>
    LCAInfo(InitT x) { val = x; }
    LCAInfo operator+(LCAInfo &x) {
        return {LCA.LCA(val, x.val)};
    }
}; // for range lca.

#endif // AFGR_LCA

#line 1 "src/alfred/graph/lca.hpp"



#line 1 "src/alfred/data_structure/sparse-table.hpp"



#include <limits>
#include <numeric>
#include <vector>

template <class T>
struct MaxInfo {
    T val;
    MaxInfo(void) { val = std::numeric_limits<T>::min(); }
    template <class InitT>
    MaxInfo(InitT x) { val = x; }
    MaxInfo operator+(MaxInfo &x) {
        return {std::max(val, x.val)};
    }
};
template <class T>
struct MinInfo {
    T val;
    MinInfo(void) { val = std::numeric_limits<T>::max(); }
    template <class InitT>
    MinInfo(InitT x) { val = x; }
    MinInfo operator+(MinInfo &x) {
        return {std::min(val, x.val)};
    }
};
template <class T>
struct GcdInfo {
    T val;
    GcdInfo(void) { val = T(); }
    template <class InitT>
    GcdInfo(InitT x) { val = x; }
    GcdInfo operator+(GcdInfo &x) {
#if __cplusplus >= 201703L
        return {std::gcd(x.val, val)};
#else
        return {__gcd(x.val, val)};
#endif
    }
};
template <class T>
class SparseTable {
private:
    int n;
    std::vector<std::vector<T>> ST;

public:
    SparseTable(void) {}
    SparseTable(int N) : n(N), ST(N, std::vector<T>(std::__lg(N) + 1)) {}
    template <class InitT>
    SparseTable(std::vector<InitT> &_init) : SparseTable(_init.size()) { init(_init, true); }
    template <class InitT>
    inline void init(std::vector<InitT> &_init, bool internal = false) {
        if (!internal) {
            n = _init.size();
            ST.assign(n, std::vector<T>(std::__lg(n) + 1));
        }
        for (int i = 0; i < n; i++) ST[i][0] = T(_init[i]);
        for (int i = 1; (1 << i) <= n; i++) {
            for (int j = 0; j + (1 << i) - 1 < n; j++) {
                ST[j][i] = ST[j][i - 1] + ST[j + (1 << (i - 1))][i - 1];
            }
        }
    }
    inline T query(int l, int r) { // 0 based
        if (l > r) return T();
        int w = std::__lg(r - l + 1);
        return ST[l][w] + ST[r - (1 << w) + 1][w];
    }
    inline T disjoint_query(int l, int r) {
        if (l > r) return T();
        T ans = T();
        for (int i = std::__lg(r - l + 1); i >= 0; i--) {
            if ((1 << i) <= r - l + 1) {
                ans = ans + ST[l][i];
                l += 1 << i;
            }
        }
        return ans;
    }
};


#line 6 "src/alfred/graph/lca.hpp"

// requires a previous graph definition.
class LCAImpl {
private:
    std::vector<int> dfn, seq; // dfn and seq are (internally) zero indexed.
    static std::vector<int> d;
    struct EulerTourInfo {
        int val;
        EulerTourInfo(void) : val(0) {}
        EulerTourInfo(int x) : val(x) {}
        EulerTourInfo operator+(EulerTourInfo &x) {
            return d[val] < d[x.val] ? val : x.val;
        }
    };
    SparseTable<EulerTourInfo> lca; // 0 indexed.
    inline void _dfs(int x, int fa) {
        dfn[x] = seq.size();
        seq.push_back(x), d[x] = d[fa] + 1;
        for (auto &y : G[x]) {
            if (y == fa) continue;
            _dfs(y, x), seq.push_back(x);
        }
    }

public:
    inline void init(int n, int rt = 1) {
        d.assign(n + 1, 0), dfn.assign(n + 1, 0);
        seq.clear(), _dfs(rt, 0), lca.init(seq);
    }
    inline int LCA(int u, int v) {
        if (u == -1) return v;
        if (v == -1) return u;
        if (dfn[u] > dfn[v]) std::swap(u, v);
        return lca.query(dfn[u], dfn[v]).val;
    }
    inline int dis(int u, int v) {
        return d[u] + d[v] - 2 * d[LCA(u, v)];
    }
} LCA;
std::vector<int> LCAImpl::d;

struct LCAInfo {
    int val;
    LCAInfo(void) : val(-1) {}
    template <class InitT>
    LCAInfo(InitT x) { val = x; }
    LCAInfo operator+(LCAInfo &x) {
        return {LCA.LCA(val, x.val)};
    }
}; // for range lca.

Back to top page