cp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Hoshinonono/cp-library

:heavy_check_mark: HL分解 (HLD, Heavy-Light-Decomposition)
(Tree/hld.hpp)

概要

HL分解 (HLD, Heavy-Light-Decomposition) を行うためのライブラリ。
それぞれの頂点に対して、 子の頂点のうち部分木の頂点数が最も大きい頂点を1つ選択して Heavy Edge で結ぶことで $\log N$ 個程度のパスに分解でき、パスの更新クエリに対して高速に処理できる。
実装は HL分解(Heavy-Light-Decomposition) | Luzhiled’s memo をかなり参考にした。

関数名など 機能 計算量
Heavy_Light_Decomposition
(std::vector<std::vector<int>> g) 		コンストラクタに木を渡すと、HL分解される。 $\text{O} (N)$
(1) int la(int v, int d)
(2) int la(int from, int to, int d) 		(1)頂点 $v$ から根に向かって距離 $d$ 進んだ頂点を返す。
(2)頂点 $\text{from}$ から頂点 $\text{to}$ に向かって距離 $d$ 進んだ頂点を返す。
存在しない場合は -1 を返す。		 $\text{O}(\log N)$
int lca(int u, int v) 頂点 $u$ と頂点 $v$ のLCAを返す。 $\text{O}(\log N)$
int dist(int u, int v) 頂点 $u$ と頂点 $v$ の距離を出力する。 $\text{O}(\log N)$
int [v] 頂点 $v$ が行きがけ順で何番目に訪問された頂点であるかを返す。配列などでここに対応する添え字の値を更新すると、頂点 $v$ に対する値を更新したことになる。 $\text{O}(1)$
T query(int u, int v,
const T &identity,
const Q &qf, const F &f, bool edge = false) 		頂点 $u$ - $v$ 間の頂点の値に対して演算を行う。第3引数以降は以下のようなものを渡す。
・ T identity ：演算に対応する単位元(ラムダ式ではないので注意)
・ T qf(int l, int r) ：列に対する区間収得クエリ。
・ T f(T lhs, T rhs) : 列と列の結合クエリ。
・ edge ：辺に対する演算であるか(省略可能)。省略した場合、頂点に対する演算であるとして計算する。		 $O(\log N)$
T noncom_query(int u, int v,
const T &identity,
const Q1 &qf, const Q2 &rev_qf,
const F &f, bool edge) 		頂点 $u$ - $v$ 間の頂点の値に対して非可換な演算を行う。第3引数以降は以下のようなものを渡す。
・ T identity ：演算に対応する単位元(ラムダ式ではないので注意)
・ T qf(int l, int r) ：左辺が子、右辺が親とした区間収得クエリ。
・ T rev_qf(int l, int r) ：左辺が親、右辺が子とした区間収得クエリ。
・ T f(T lhs, T rhs) : 左辺が子、右辺が親としたときの列と列の結合クエリ。
・ edge ：辺に対する演算であるか(省略可能)。省略した場合、頂点に対する演算であるとして計算する。		 $O(\log N)$
void update(int u, int v,
const Q &q, bool edge) 		頂点 $u$ - $v$ 間の頂点の値に対して更新演算を行う。第3引数以降は以下のようなものを渡す。
・ Q q(int l, int r) ：区間 $[l, r)$ に対する更新演算。遅延セグ木の seg.apply(l, r) などを入れることを想定。
・ edge ：辺に対する演算であるか(省略可能)。省略した場合、頂点に対する演算であるとして計算する。		 $O(\log N)$

Verified with

Code

struct Heavy_Light_Decomposition{
    int N, tim = 0;
    std::vector<int> sz, ent, leader, order, par;
    std::vector<std::vector<int>> &G;
    Heavy_Light_Decomposition(std::vector<std::vector<int>> &g) : 
            N(g.size()), G(g), sz(N), ent(N), leader(N), order(N), par(N) {
        dfs_size(0, -1);
        dfs_hld(0);
    }
    const int operator[](int v) const {
        assert(0 <= v && v < N);
        return ent[v];
    }
    int operator[](int v) { 
        assert(0 <= v && v < N);
        return ent[v];
    }
    int la(int v, int k) {
        while(true) {
            int u = leader[v];
            if(ent[v] - k >= ent[u]) return order[ent[v] - k];
            k -= ent[v] - ent[u] + 1;
            v = par[u];
        }
    }
    int la(int from, int to, int d){
        int d1 = 0, d2 = 0;
        int v = from, u = to;
        do{
            if(ent[u] < ent[v]){
                if(leader[u] == leader[v]){
                    d1 += ent[v] - ent[u];
                    break;
                }
                d1 += ent[v] - ent[leader[v]] + 1;
                v = par[leader[v]];
            }else{
                if(leader[u] == leader[v]){
                    d2 += ent[u] - ent[v];
                    break;
                }
                d2 += ent[u] - ent[leader[u]] + 1;
                u = par[leader[u]];
            }
        }while(true);
        if(d > d1 + d2) return -1;
        return d <= d1 ? la(from, d) : la(to, d1 + d2 - d);
    }
    int lca(int u, int v) {
        do{
            if(ent[u] > ent[v]) std::swap(u, v);
            if(leader[u] == leader[v]) return u;
            v = par[leader[v]];
        }while(true);
    }
    int dist(int u, int v){
        int ans = 0;
        do{
            if(ent[u] > ent[v]) std::swap(u, v);
            if(leader[u] == leader[v]) return ans + ent[v] - ent[u];
            ans += ent[v] - ent[leader[v]] + 1;
            v = par[leader[v]];
        }while(true);
    }
    template< typename T, typename Q, typename F >
    T query(int u, int v, const T &identity, const Q &qf, const F &f, bool edge = false) {
        T ans = identity;
        do{
            if(ent[u] > ent[v]) std::swap(u, v);
            if(leader[u] == leader[v]) break;
            ans = f( qf(ent[leader[v]], ent[v] + 1), ans);
            v = par[leader[v]];
        }while(true);
        return f( qf(ent[u] + edge, ent[v] + 1), ans);
    }
    template< typename T, typename Q1, typename Q2, typename F >
    T noncom_query(int u, int v, const T &identity, 
                   const Q1 &qf, const Q2 &rev_qf, const F &f, bool edge = false) {
        T sml = identity, smr = identity;
        do{
            if(leader[u] == leader[v]) break;
            if(ent[u] < ent[v]){
                smr = f( qf(ent[leader[v]], ent[v] + 1), smr);
                v = par[leader[v]];
            }else{
                sml = f( sml, rev_qf(ent[leader[u]], ent[u] + 1));
                u = par[leader[u]];
            }
        }while(true);
        if(ent[u] < ent[v]){
            return f(sml,  f( qf(ent[u] + edge, ent[v] + 1), smr));
        }else{
            return f(f(sml, rev_qf(ent[v] + edge, ent[u] + 1)), smr);
        }
    }
    template< typename Q >
    void update(int u, int v, const Q &q, bool edge = false) {
        do{
            if(ent[u] > ent[v]) std::swap(u, v);
            if(leader[u] == leader[v]) break;
            q(ent[leader[v]], ent[v] + 1);
            v = par[leader[v]];
        }while(true);
        q(ent[u] + edge, ent[v] + 1);
    }
    private:
    void dfs_size(int v, int p){
        par[v] = p;
        sz[v] = 1;
        if(!G[v].empty() && G[v][0] == p) std::swap(G[v][0], G[v].back());
        for(auto &u : G[v]){
            if(u == p) continue;
            dfs_size(u, v);
            sz[v] += sz[u];
            if(sz[u] > sz[G[v][0]]) std::swap(G[v][0], u);
        }
    }
    void dfs_hld(int v){
        ent[v] = tim++;
        order[ent[v]] = v;
        for(auto &u : G[v]) {
            if(u == par[v]) continue;
            leader[u] = (G[v][0] == u ? leader[v] : u);
            dfs_hld(u);
        }
    }
};
#line 1 "Tree/hld.hpp"
struct Heavy_Light_Decomposition{
    int N, tim = 0;
    std::vector<int> sz, ent, leader, order, par;
    std::vector<std::vector<int>> &G;
    Heavy_Light_Decomposition(std::vector<std::vector<int>> &g) : 
            N(g.size()), G(g), sz(N), ent(N), leader(N), order(N), par(N) {
        dfs_size(0, -1);
        dfs_hld(0);
    }
    const int operator[](int v) const {
        assert(0 <= v && v < N);
        return ent[v];
    }
    int operator[](int v) { 
        assert(0 <= v && v < N);
        return ent[v];
    }
    int la(int v, int k) {
        while(true) {
            int u = leader[v];
            if(ent[v] - k >= ent[u]) return order[ent[v] - k];
            k -= ent[v] - ent[u] + 1;
            v = par[u];
        }
    }
    int la(int from, int to, int d){
        int d1 = 0, d2 = 0;
        int v = from, u = to;
        do{
            if(ent[u] < ent[v]){
                if(leader[u] == leader[v]){
                    d1 += ent[v] - ent[u];
                    break;
                }
                d1 += ent[v] - ent[leader[v]] + 1;
                v = par[leader[v]];
            }else{
                if(leader[u] == leader[v]){
                    d2 += ent[u] - ent[v];
                    break;
                }
                d2 += ent[u] - ent[leader[u]] + 1;
                u = par[leader[u]];
            }
        }while(true);
        if(d > d1 + d2) return -1;
        return d <= d1 ? la(from, d) : la(to, d1 + d2 - d);
    }
    int lca(int u, int v) {
        do{
            if(ent[u] > ent[v]) std::swap(u, v);
            if(leader[u] == leader[v]) return u;
            v = par[leader[v]];
        }while(true);
    }
    int dist(int u, int v){
        int ans = 0;
        do{
            if(ent[u] > ent[v]) std::swap(u, v);
            if(leader[u] == leader[v]) return ans + ent[v] - ent[u];
            ans += ent[v] - ent[leader[v]] + 1;
            v = par[leader[v]];
        }while(true);
    }
    template< typename T, typename Q, typename F >
    T query(int u, int v, const T &identity, const Q &qf, const F &f, bool edge = false) {
        T ans = identity;
        do{
            if(ent[u] > ent[v]) std::swap(u, v);
            if(leader[u] == leader[v]) break;
            ans = f( qf(ent[leader[v]], ent[v] + 1), ans);
            v = par[leader[v]];
        }while(true);
        return f( qf(ent[u] + edge, ent[v] + 1), ans);
    }
    template< typename T, typename Q1, typename Q2, typename F >
    T noncom_query(int u, int v, const T &identity, 
                   const Q1 &qf, const Q2 &rev_qf, const F &f, bool edge = false) {
        T sml = identity, smr = identity;
        do{
            if(leader[u] == leader[v]) break;
            if(ent[u] < ent[v]){
                smr = f( qf(ent[leader[v]], ent[v] + 1), smr);
                v = par[leader[v]];
            }else{
                sml = f( sml, rev_qf(ent[leader[u]], ent[u] + 1));
                u = par[leader[u]];
            }
        }while(true);
        if(ent[u] < ent[v]){
            return f(sml,  f( qf(ent[u] + edge, ent[v] + 1), smr));
        }else{
            return f(f(sml, rev_qf(ent[v] + edge, ent[u] + 1)), smr);
        }
    }
    template< typename Q >
    void update(int u, int v, const Q &q, bool edge = false) {
        do{
            if(ent[u] > ent[v]) std::swap(u, v);
            if(leader[u] == leader[v]) break;
            q(ent[leader[v]], ent[v] + 1);
            v = par[leader[v]];
        }while(true);
        q(ent[u] + edge, ent[v] + 1);
    }
    private:
    void dfs_size(int v, int p){
        par[v] = p;
        sz[v] = 1;
        if(!G[v].empty() && G[v][0] == p) std::swap(G[v][0], G[v].back());
        for(auto &u : G[v]){
            if(u == p) continue;
            dfs_size(u, v);
            sz[v] += sz[u];
            if(sz[u] > sz[G[v][0]]) std::swap(G[v][0], u);
        }
    }
    void dfs_hld(int v){
        ent[v] = tim++;
        order[ent[v]] = v;
        for(auto &u : G[v]) {
            if(u == par[v]) continue;
            leader[u] = (G[v][0] == u ? leader[v] : u);
            dfs_hld(u);
        }
    }
};
Back to top page