HL分解 LIB::HeavyLightDecomposition

LIB::HeavyLightDecomposition

heavy edge と light edge に分解してセグメント木などのデータ構造と併用することでパスクエリを高速に処理する　構築 $O(n \log{n})$ 部分木クエリ $O(\log{n})$ パスクエリ $O(\log^2{n})$
https://qiita.com/Pro_ktmr/items/4e1e051ea0561772afa3
https://hcpc-hokudai.github.io/archive/graph_tree_001.pdf
https://tubo28.me/compprog/algorithm/hld/

メンバ関数

HeavyLightDecomposition(graph &ag, ll ar)

分解する木agと分解するときの根ノードarを入力

vpll all_path_idx(ll an, ll bn)

ノードの閉区間 [an,bn] における最短パスを index 閉区間の集合で返す

pll path_idx(ll nd)

ノード nd が含まれるようなパス閉区間を index で返す

メンバ変数

parent[nd]

ノード nd の親（根のときは -1 を返す）

subsize[nd]

ノード nd を根とする部分木のノード数

depth[nd]

ノード nd の根ノードからの距離

head[nd]

ノード nd が属するパスにおける先頭ノード

tail[nd]

ノード nd が属するパスにおける末尾ノード

prev[nd]

ノード nd の前ノード（パスの範囲を超えるとき -1 を返す）

next[nd]

ノード nd の次ノード（パスの範囲を超えるとき -1 を返す）

all_path

分解した全てのパス集合（ head の深さ昇順に入っている）

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

namespace LIB {
    class HeavyLightDecomposition {
        using ll = long long;
        using graph=vector<vector<ll>>;
        using vpll=vector<pair<ll,ll>>;
        ll n;
        std::vector<ll> at;
        void run(const ll root) {
            static ll stk[1000001];
            ll k=0;
            stk[k++]=root;
            parent[root]=-1;
            depth[root]=0;

            while(k) {
                ll v=stk[--k];
                if(v>=0) {
                    stk[k++]=~v;
                    for(auto &to:g[v]) {
                        ll ch=to;
                        if(depth[ch]==-1) {
                            depth[ch]=depth[v]+1;
                            parent[ch]=v;
                            stk[k++]=ch;
                        }
                    }
                } else {
                    ll m=0;
                    v=~v;
                    subsize[v]=1;
                    for(auto &to:g[v]) {
                        ll ch=to;
                        if(parent[v]==ch) continue;
                        subsize[v]+=subsize[ch];
                        if(m<subsize[ch]) m=subsize[ch],next[v]=ch;
                    }
                }
            }

            k = 0;
            stk[k++] = root;
            while(k) {
                ll h=stk[--k];
                for(auto &to:g[h]) if(parent[h]!=to) stk[k++]=to;
                if (path[h]!=-1) continue;
                all_path.push_back(std::vector<ll>());
                std::vector<ll> &pt=all_path.back();

                for(ll cur=h;cur!=-1;) pt.push_back(cur),cur=next[cur];

                for(ll i=0;i<(ll)pt.size();i++) {
                    ll v=pt[i];
                    head[v]=pt.front();
                    tail[v]=pt.back();
                    next[v]=i+1 != (ll)pt.size()?pt[i+1]:-1;
                    prev[v]=i!=0?pt[i-1]:-1;
                    path[v]=all_path.size()-1;
                    at[v]=i;
                }
            }

            ll i=0;
            for(auto& ch:all_path) for(auto& e:ch) idx[e]=i++;
        }
    public:
        graph g;
        std::vector<std::vector<ll>> all_path;
        std::vector<ll> depth,head,idx,next,parent,path,prev,subsize,tail;

        HeavyLightDecomposition(graph &ag, ll ar):
            n(ag.size()),at(n,0),g(ag),all_path(0),
            depth(n,-1),head(n,0),idx(n,0),next(n,-1),parent(n,0),path(n,-1),prev(n,-1),subsize(n,0),tail(n,0)
        {
            run(ar);
        }

        vpll all_path_idx(ll an, ll bn) {
            vpll res;
            while(head[an]!=head[bn]) {
                if(depth[head[an]]<=depth[head[bn]]) res.push_back({idx[head[bn]],idx[bn]}),bn=parent[head[bn]];
                else res.push_back({idx[head[an]],idx[an]}),an=parent[head[an]];
            }
            res.push_back({idx[an],idx[bn]});
            for(auto& e:res) if(e.first>e.second) swap(e.first,e.second);
            return res;
        }

        ll lca(ll u, ll v) {
            while(path[u]!=path[v]) {
                if(depth[head[u]]>depth[head[v]]) u=parent[head[u]];
                else v=parent[head[v]];
            }
            return depth[u]<depth[v]?u:v;
        }

        pll path_idx(ll nd) { return {idx[head[nd]],idx[tail[nd]]}; }
    };
}

実装例

https://judge.yosupo.jp/submission/159981

7K4B blog

猫でも分かる何か