HL分解
(tree/heavy-light-decomposition.hpp)

• View this file on GitHub
• Last update: 2023-04-07 06:06:13-07:00
• Include: #include "tree/heavy-light-decomposition.hpp"

概要

木構造を$\log N$本以下のパスに分解して、列に対するクエリの量を$α$とすると$O(α\log N)$で頂点から頂点までの辺に対するクエリが実行できます。

例

• HeavyLightDecomposition<class S>(UnweightedGraph T) := HLDの初期化をする $O(N)$
• void set(int u,int v,S x,function<void(int,S)>) := $u$と$v$を繋ぐ辺の値を変更する。三個目の引数はデータ構造の$i$番目を$x$にする関数 $O(α)$
• int lcu(int u,int v) := $u$と$v$のlcuを返す。$O(\log N)$
• S query(int u,int v,S id,function<S(int,int)>,function<S(S,S)>) := $u$と$v$の間の辺に対するクエリを行う。query(u,v,単位元,データ構造のprod,二項演算) $O(α\log N)$

Depends on

• graph/graph-template.hpp

Verified with

• verify/yosupo/hld-lcu.test.cpp

Code

#include "../graph/graph-template.hpp"

#include<vector>
#include<utility>
#include<algorithm>
#include<functional>

template<class S>
struct HeavyLightDecomposition{
    UnweightedGraph T;
    int N;
    std::vector<int> parent,siz_t,depth,shallow,hld,rev_hld;
    int dfs(int now,int prev){
        parent[now]=prev;
        depth[now]=prev!=-1?depth[prev]+1:0;
        int siz=1;
        for(int i:T[now]){
            if(i==prev)continue;
            siz+=dfs(i,now);
        }
        siz_t[now]=siz;
        return siz;
    }
    void dfs2(int now,int prev,bool new_path){
        rev_hld[now]=hld.size();
        hld.push_back(now);
        shallow[now]=new_path?now:shallow[prev];

        int ma=0,ma_idx=-1;
        for(int i:T[now]){
            if(i!=prev && siz_t[i]>ma){
                ma=siz_t[i],ma_idx=i;
            }
        }
        if(ma_idx==-1)return;
        dfs2(ma_idx,now,false);

        for(int i:T[now]){
            if(i!=ma_idx && i!=prev)dfs2(i,now,true);
        }
    }
    HeavyLightDecomposition(UnweightedGraph &T):T(T){
        N=HeavyLightDecomposition::T.size();
        parent.resize(N);
        siz_t.resize(N);
        depth.resize(N);
        shallow.resize(N);
        rev_hld.resize(N);
        dfs(0,-1);
        dfs2(0,-1,1);
    }

    std::vector<std::pair<int,int>> q(int u,int v){
        std::vector<std::pair<int,int>> ret;
        while(shallow[u]!=shallow[v]){
            if(depth[shallow[u]]<=depth[shallow[v]]){
                ret.push_back({rev_hld[shallow[v]],rev_hld[v]});
                v=parent[shallow[v]];
            }else{
                ret.push_back({rev_hld[shallow[u]],rev_hld[u]});
                u=parent[shallow[u]];
            }
        }
        ret.push_back({std::min(rev_hld[u],rev_hld[v]),std::max(rev_hld[u],rev_hld[v])});
        return ret;
    }

    void set(int u,int v,S x,std::function<void(int,int)> f){
        if(parent[v]==u){
            f(rev_hld[v],x);
        }else{
            f(rev_hld[u],x);
        }
    }

    S query(int u,int v,S id,std::function<S(int,int)> f,std::function<S(S,S)> op){
        std::vector<std::pair<int,int>> que=q(u,v);
        S ret=id;
        for(int i=0;i<que.size()-1;i++){
            ret=op(ret,f(que[i].first,que[i].second+1));
        }
        if(que.back().first!=N-1 && que.back().first!=que.back().second){
            ret=op(ret,f(que.back().first+1,que.back().second+1));
        }
        return ret;
    }

    int lcu(int u,int v){
        return hld[q(u,v).back().first];
    }
};

#line 1 "graph/graph-template.hpp"
#include <iostream>
#include <vector>
template<class T>
struct edge{
    int from,to;
    T cost;
    
    edge(int to,T cost):from(-1),to(to),cost(cost){}
    edge(int from,int to,T cost):from(from),to(to),cost(cost){}

    edge &operator=(const int &x){
        to=x;
        return *this;
    }
};

template<class T>
using Edges = std::vector<edge<T>>;

template<class T>
using WeightedGraph = std::vector<Edges<T>>;
using UnweightedGraph = std::vector<std::vector<int>>;

UnweightedGraph input_graph(int N,int M,bool directed=false,bool one_origin=true){
    UnweightedGraph ret(N);
    for(int i=0;i<M;i++){
        int from,to;std::cin>>from>>to;
        if(one_origin)from--,to--;
        ret[from].push_back(to);
        if(!directed)ret[to].push_back(from);
    }
    return ret;
};

template<class T>
WeightedGraph<T> input_wgraph(int N,int M,bool directed=false,bool one_origin=true){
    WeightedGraph<T> ret(N);
    for(int i=0;i<M;i++){
        int from,to;T cost;std::cin>>from>>to>>cost;
        if(one_origin)from--,to--;
        ret[from].emplace_back(from,to,cost);
        if(!directed)ret[to].emplace_back(to,from,cost);
    }
    return ret;
};
#line 2 "tree/heavy-light-decomposition.hpp"

#line 4 "tree/heavy-light-decomposition.hpp"
#include<utility>
#include<algorithm>
#include<functional>

template<class S>
struct HeavyLightDecomposition{
    UnweightedGraph T;
    int N;
    std::vector<int> parent,siz_t,depth,shallow,hld,rev_hld;
    int dfs(int now,int prev){
        parent[now]=prev;
        depth[now]=prev!=-1?depth[prev]+1:0;
        int siz=1;
        for(int i:T[now]){
            if(i==prev)continue;
            siz+=dfs(i,now);
        }
        siz_t[now]=siz;
        return siz;
    }
    void dfs2(int now,int prev,bool new_path){
        rev_hld[now]=hld.size();
        hld.push_back(now);
        shallow[now]=new_path?now:shallow[prev];

        int ma=0,ma_idx=-1;
        for(int i:T[now]){
            if(i!=prev && siz_t[i]>ma){
                ma=siz_t[i],ma_idx=i;
            }
        }
        if(ma_idx==-1)return;
        dfs2(ma_idx,now,false);

        for(int i:T[now]){
            if(i!=ma_idx && i!=prev)dfs2(i,now,true);
        }
    }
    HeavyLightDecomposition(UnweightedGraph &T):T(T){
        N=HeavyLightDecomposition::T.size();
        parent.resize(N);
        siz_t.resize(N);
        depth.resize(N);
        shallow.resize(N);
        rev_hld.resize(N);
        dfs(0,-1);
        dfs2(0,-1,1);
    }

    std::vector<std::pair<int,int>> q(int u,int v){
        std::vector<std::pair<int,int>> ret;
        while(shallow[u]!=shallow[v]){
            if(depth[shallow[u]]<=depth[shallow[v]]){
                ret.push_back({rev_hld[shallow[v]],rev_hld[v]});
                v=parent[shallow[v]];
            }else{
                ret.push_back({rev_hld[shallow[u]],rev_hld[u]});
                u=parent[shallow[u]];
            }
        }
        ret.push_back({std::min(rev_hld[u],rev_hld[v]),std::max(rev_hld[u],rev_hld[v])});
        return ret;
    }

    void set(int u,int v,S x,std::function<void(int,int)> f){
        if(parent[v]==u){
            f(rev_hld[v],x);
        }else{
            f(rev_hld[u],x);
        }
    }

    S query(int u,int v,S id,std::function<S(int,int)> f,std::function<S(S,S)> op){
        std::vector<std::pair<int,int>> que=q(u,v);
        S ret=id;
        for(int i=0;i<que.size()-1;i++){
            ret=op(ret,f(que[i].first,que[i].second+1));
        }
        if(que.back().first!=N-1 && que.back().first!=que.back().second){
            ret=op(ret,f(que.back().first+1,que.back().second+1));
        }
        return ret;
    }

    int lcu(int u,int v){
        return hld[q(u,v).back().first];
    }
};

Back to top page