HL 分解
(graph/hld.hpp)

View this file on GitHub
Last update: 2022-10-20 00:25:59+09:00
Include: #include "graph/hld.hpp"

概要

HL 分解を用いて木をパスに分解する。

詳細

struct hld
HL 分解を行う構造体。
- (constructor)(int n)
  頂点数 $n$ で初期化。
- void add_edge(int u, int v)
  頂点 $u, v$ 間に辺を張る。
- vector<int> build(int root)
  頂点 $root$ を根として初期化し、各頂点の別の番号の vector を返す。 $O(n)$ 時間。
- int lca(int u, int v)
  頂点 $u, v$ の LCA の番号を返す。 $O(\log n)$ 時間。
- int get_path(int u, int v, bool edge)
  頂点属性のクエリの場合、頂点 $u, v$ 間のパスを $O(\log n)$ 個に分解し、「「新たな番号での始点、終点 (閉区間) を表す pair」の vector」を返す。辺属性のクエリの場合もほぼ同様だが、こちらの場合は新たな頂点番号について、その頂点の親に繋がる辺という意味になる。
- pair<int, int> get_subtree(int v, bool edge)
  頂点 $v$ の部分木を $1$ 個の区間として返す。

備考

雑なのでまたちゃんと書く

参考

adamant さんの Codeforces blog

Depends on

template.hpp

Verified with

test/unit/hld.test.cpp

Code

#pragma once

#include "../template.hpp"

struct hld {
    vector<vector<ll>> g;
    vector<ll> par, sz, dep, in, out, head;
    hld(ll n) : g(n), par(n), sz(n), dep(n), in(n), out(n), head(n) {}
    void add_edge(ll u, ll v) { g[u].push_back(v), g[v].push_back(u); }
    vector<ll> build(ll root) {
        auto dfs_sz = [&](auto dfs_sz, ll v, ll p) -> void {
            sz[v] = 1;
            par[v] = p;
            if (p != -1) dep[v] = dep[p] + 1;
            for (ll &u : g[v]) {
                if (u == p) continue;
                dfs_sz(dfs_sz, u, v);
                sz[v] += sz[u];
                if (sz[u] > sz[g[v][0]]) swap(u, g[v][0]);
            }
        };
        ll t = 0;
        auto dfs_hld = [&](auto dfs_hld, ll v) -> ll {
            in[v] = t++;
            for (ll i : rep(g[v].size())) {
                ll u = g[v][i];
                if (u == par[v]) continue;
                head[u] = (i == 0 ? head[v] : u);
                dfs_hld(dfs_hld, u);
            }
            return out[v] = t;
        };
        dfs_sz(dfs_sz, root, -1);
        head[root] = root;
        dfs_hld(dfs_hld, root);
        return in;
    }
    ll lca(ll u, ll v) const {
        while (true) {
            if (in[u] > in[v]) swap(u, v);
            if (head[u] == head[v]) return u;
            v = par[head[v]];
        }
    }
    ll dist(ll u, ll v) const { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }
    vector<pair<ll, ll>> get_path(ll u, ll v, bool edge) const {
        vector<pair<ll, ll>> a, b;
        while (true) {
            if (head[u] == head[v]) {
                if (edge) {
                    if (in[u] > in[v]) a.emplace_back(in[u], in[v] + 1);
                    if (in[u] < in[v]) a.emplace_back(in[u] + 1, in[v]);
                } else {
                    a.emplace_back(in[u], in[v]);
                }
                break;
            }
            if (in[u] > in[v]) {
                a.emplace_back(in[u], in[head[u]]);
                u = par[head[u]];
            } else {
                b.emplace_back(in[head[v]], in[v]);
                v = par[head[v]];
            }
        }
        a.insert(a.end(), b.rbegin(), b.rend());
        return a;
    }
    pair<ll, ll> get_subtree(ll v, bool edge) const { return {in[v] + edge, out[v] - 1}; }
};

#line 2 "graph/hld.hpp"

#line 2 "template.hpp"

#include <bits/stdc++.h>
using namespace std;

#define all(a) begin(a), end(a)
#define rall(a) rbegin(a), rend(a)
#define uniq(a) (a).erase(unique(all(a)), (a).end())
#define t0 first
#define t1 second
using ll = long long;
using ull = unsigned long long;
using pll = pair<ll, ll>;
using vll = vector<ll>;
constexpr double pi = 3.14159265358979323846;
constexpr ll dy[9] = {0, 1, 0, -1, 1, 1, -1, -1, 0};
constexpr ll dx[9] = {1, 0, -1, 0, 1, -1, -1, 1, 0};
constexpr ll sign(ll a) { return (a > 0) - (a < 0); }
constexpr ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); }
constexpr ll cdiv(ll a, ll b) { return -fdiv(-a, b); }
constexpr ll pw(ll n) { return 1ll << n; }
constexpr ll flg(ll n) { return 63 - __builtin_clzll(n); }
constexpr ll clg(ll n) { return n == 1 ? 0 : flg(n - 1) + 1; }
constexpr ll safemod(ll x, ll mod) { return (x % mod + mod) % mod; }
template <typename T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
template <typename T> constexpr T sq(const T &a) { return a * a; }
template <typename T, typename U> constexpr bool chmax(T &a, const U &b) { return a < b ? a = b, true : false; }
template <typename T, typename U> constexpr bool chmin(T &a, const U &b) { return a > b ? a = b, true : false; }
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &a) {
    os << "(" << a.first << ", " << a.second << ")";
    return os;
}
template <typename T, typename U, typename V> ostream &operator<<(ostream &os, const tuple<T, U, V> &a) {
    os << "(" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << ")";
    return os;
}
template <typename T> ostream &operator<<(ostream &os, const vector<T> &a) {
    os << "(";
    for (auto itr = a.begin(); itr != a.end(); ++itr) os << *itr << (next(itr) != a.end() ? ", " : "");
    os << ")";
    return os;
}
template <typename T> ostream &operator<<(ostream &os, const set<T> &a) {
    os << "(";
    for (auto itr = a.begin(); itr != a.end(); ++itr) os << *itr << (next(itr) != a.end() ? ", " : "");
    os << ")";
    return os;
}
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &a) {
    os << "(";
    for (auto itr = a.begin(); itr != a.end(); ++itr) os << *itr << (next(itr) != a.end() ? ", " : "");
    os << ")";
    return os;
}
template <typename T, typename U> ostream &operator<<(ostream &os, const map<T, U> &a) {
    os << "(";
    for (auto itr = a.begin(); itr != a.end(); ++itr) os << *itr << (next(itr) != a.end() ? ", " : "");
    os << ")";
    return os;
}
#ifdef ONLINE_JUDGE
#define dump(...) (void(0))
#else
void debug() { cerr << endl; }
template <typename Head, typename... Tail> void debug(Head &&head, Tail &&... tail) {
    cerr << head;
    if (sizeof...(Tail)) cerr << ", ";
    debug(tail...);
}
#define dump(...) cerr << __LINE__ << ": " << #__VA_ARGS__ << " = ", debug(__VA_ARGS__)
#endif
struct rep {
    struct itr {
        ll v;
        itr(ll v) : v(v) {}
        void operator++() { ++v; }
        ll operator*() const { return v; }
        bool operator!=(itr i) const { return v < *i; }
    };
    ll l, r;
    rep(ll l, ll r) : l(l), r(r) {}
    rep(ll r) : rep(0, r) {}
    itr begin() const { return l; };
    itr end() const { return r; };
};
struct per {
    struct itr {
        ll v;
        itr(ll v) : v(v) {}
        void operator++() { --v; }
        ll operator*() const { return v; }
        bool operator!=(itr i) const { return v > *i; }
    };
    ll l, r;
    per(ll l, ll r) : l(l), r(r) {}
    per(ll r) : per(0, r) {}
    itr begin() const { return r - 1; };
    itr end() const { return l - 1; };
};
struct io_setup {
    static constexpr int PREC = 20;
    io_setup() {
        cout << fixed << setprecision(PREC);
        cerr << fixed << setprecision(PREC);
    };
} iOS;
#line 4 "graph/hld.hpp"

struct hld {
    vector<vector<ll>> g;
    vector<ll> par, sz, dep, in, out, head;
    hld(ll n) : g(n), par(n), sz(n), dep(n), in(n), out(n), head(n) {}
    void add_edge(ll u, ll v) { g[u].push_back(v), g[v].push_back(u); }
    vector<ll> build(ll root) {
        auto dfs_sz = [&](auto dfs_sz, ll v, ll p) -> void {
            sz[v] = 1;
            par[v] = p;
            if (p != -1) dep[v] = dep[p] + 1;
            for (ll &u : g[v]) {
                if (u == p) continue;
                dfs_sz(dfs_sz, u, v);
                sz[v] += sz[u];
                if (sz[u] > sz[g[v][0]]) swap(u, g[v][0]);
            }
        };
        ll t = 0;
        auto dfs_hld = [&](auto dfs_hld, ll v) -> ll {
            in[v] = t++;
            for (ll i : rep(g[v].size())) {
                ll u = g[v][i];
                if (u == par[v]) continue;
                head[u] = (i == 0 ? head[v] : u);
                dfs_hld(dfs_hld, u);
            }
            return out[v] = t;
        };
        dfs_sz(dfs_sz, root, -1);
        head[root] = root;
        dfs_hld(dfs_hld, root);
        return in;
    }
    ll lca(ll u, ll v) const {
        while (true) {
            if (in[u] > in[v]) swap(u, v);
            if (head[u] == head[v]) return u;
            v = par[head[v]];
        }
    }
    ll dist(ll u, ll v) const { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }
    vector<pair<ll, ll>> get_path(ll u, ll v, bool edge) const {
        vector<pair<ll, ll>> a, b;
        while (true) {
            if (head[u] == head[v]) {
                if (edge) {
                    if (in[u] > in[v]) a.emplace_back(in[u], in[v] + 1);
                    if (in[u] < in[v]) a.emplace_back(in[u] + 1, in[v]);
                } else {
                    a.emplace_back(in[u], in[v]);
                }
                break;
            }
            if (in[u] > in[v]) {
                a.emplace_back(in[u], in[head[u]]);
                u = par[head[u]];
            } else {
                b.emplace_back(in[head[v]], in[v]);
                v = par[head[v]];
            }
        }
        a.insert(a.end(), b.rbegin(), b.rend());
        return a;
    }
    pair<ll, ll> get_subtree(ll v, bool edge) const { return {in[v] + edge, out[v] - 1}; }
};

HL 分解 (graph/hld.hpp)

概要

詳細

備考

参考

Depends on

Verified with

Code

HL 分解
(graph/hld.hpp)