Heavy Light Decomposition

概要

木を大きいパスから順に分割して列に変換することで、木に対して区間クエリが使えるデータ構造。
区間クエリ部分を SegmentTree で実装している為、モノイドであれば何でも、木に対して区間演算が O(logN) で適用可能。
(勿論更新も1回当たり O(logN) で可能。)

作成part

以下二つの記事を参考に実装。 頂点も辺も載せることが出来る。頂点は簡単だが、辺は深さが深い方のノードに重みを載せることでうまく管理出来る。

【図解】木のパスに関するクエリは HL 分解！ その仕組みと実装を図で理解する｜Heavy-Light Decomposition - Qiita

この記事では木構造に関するアルゴリズム**「HL 分解 (Heavy-Light Decomposition，HLD とも)」について紹介します．このアルゴリズムを理解すると，様々な「木のパスに対す…

qiita.com

絶対に初心者でもわかるHL分解/Heavy-Light-Decomposition - Qiita

Heavy-Light-Decomposition（日本語:HL分解）を知っていますか？木に対する非常に有用なアルゴリズムですが、日本語の資料が非常に少ないです。めちゃくちゃ少ないです。あっても古…

qiita.com

method

• addEdge(u, v) : 木構造の辺追加
• set(u,x) : 各頂点に乗せる値
• set(u,v,x) : 各辺に乗せる値（関数をオーバーロードして引数の数で使い分け）
• build() : 辺を N-1 本追加した後に発火することで重軽分解を行う
• query(u, v) : 木上の u → v のパスにおいて、Segment Tree にて設定した演算を O(logN) で行う

Program

// ↓~~~~~~~~~~ Heavy-Light-Deconposition ~~~~~~~~~~↓ //
// モノイド設定
using S = long long;
S Sum_e(){return 0;}
S Sum_op(S a,S b){return a+b;}

class HLD{
    public:
        HLD() : n(0){}
        explicit HLD(const int _n, bool _ef){
            n = _n;
            ef = _ef; // 辺更新ならtrue , 頂点更新ならfalse
            part_size.assign(n,1);
            shallow.assign(n,0);
            parent.assign(n,0);
            Graph.assign(n,{});
            depth.assign(n,0);
            hld.assign(n,0);
            sg = segtree<S,Sum_op,Sum_e>(n);
        }

        inline void addEdge(int u, int v){
            Graph[u].emplace_back(v);
            Graph[v].emplace_back(u);
        }

        void build(){
            dfs(0,-1);            // parent & depth 算出
            HLDecomposition(0,0); // HL分解
        }

        long long query(int u, int v){
            long long res = 0;
            while(shallow[u] != shallow[v]){
                if(depth[shallow[u]] > depth[shallow[v]])swap(u,v);
                // 深いHLD要素を遡る
                res += sg.prod(hld[shallow[v]], hld[v]+1);
                v = parent[shallow[v]];
            }
            if(depth[u] > depth[v])swap(u,v);
            res += sg.prod(hld[u]+ef, hld[v]+1);
            return res;
        }

        inline void set(int idx, long long x){
            // 頂点set
            sg.set(hld[idx],x);
        }
        inline void set(int u, int v, long long x){
            // 辺set
            if(depth[u] > depth[v])swap(u,v);
            sg.set(hld[v],x);
        }

    private:
        bool ef;
        int n, child;
        // hld     : 元の頂点 → HLD要素
        // r_hld   : HLD要素 → 元の頂点
        // shallow : HLD要素の最も浅い頂点
        vector<int> part_size, r_hld, shallow, hld, depth, parent;
        vector<vector<int>> Graph;
        segtree<S,Sum_op,Sum_e> sg;

        inline void HLDecomposition(int v, const int a){
            hld[v] = r_hld.size();
            r_hld.emplace_back(v);
            shallow[v] = a;

            if( (Graph[v].size() == 1 && Graph[v][0] == parent[v]) || Graph[v].size() == 0 )return;

            int max_size = -1, max_idx = 0;
            for(int i=0;i<Graph[v].size();i++){
                child = Graph[v][i];
                if(child == parent[v])continue;
                if(max_size < part_size[child]){
                    max_size = part_size[child];
                    max_idx = i;
                }
            }
            HLDecomposition(Graph[v][max_idx],a);
            for(int i=0; i<Graph[v].size(); i++){
                child = Graph[v][i];
                if(child == parent[v])continue;
                if(i != max_idx){
                    HLDecomposition(child,child);
                }
            }
        }

        inline void dfs(const int &now, const int pre){
            if(pre == -1)depth[now] = 0;
            else depth[now] = depth[pre]+1;
            parent[now] = pre;
            for(auto to:Graph[now]){
                if(to == pre)continue;
                dfs(to,now);
                part_size[now] += part_size[to];
            }
        }
};
// ↑~~~~~~~~~~ Heavy-Light-Deconposition ~~~~~~~~~~↑ //

// ※ buildしてからじゃないと重みset出来ないので注意