heavy-light decomposition
(include/emthrm/graph/tree/heavy-light_decomposition.hpp)
heavy edge と light edge に分類された辺を基にして、木を分解する方法である。
時間計算量
$\langle O(\lvert V \rvert), O(\log{\lvert V \rvert}) \rangle$
仕様
template < typename CostType >
struct HeavyLightDecomposition ;
メンバ変数
名前
説明
std::vector<int> parent
parent[i]
は頂点 $i$ の親の頂点番号を表す。
std::vector<int> subtree
subtree[i]
は頂点 $i$ の部分木の大きさを表す。
std::vector<int> id
id[i]
は頂点 $i$ の ID を表す。
std::vector<int> inv
inv[i]
はID $i$ の頂点番号を表す。
std::vector<int> head
head[i]
は頂点 $i$ を含む heavy path の先頭の頂点番号を表す。
std::vector<CostType> cost
cost[i]
は辺 (inv[i]
, inv[i + 1]
) の重みを表す。
メンバ関数
名前
効果・戻り値
explicit HeavyLightDecomposition(const std::vector<std::vector<Edge<CostType>>>& graph, const int root = 0);
根を $\mathrm{root}$ とする木 $\mathrm{graph}$ に対してオブジェクトを構築する。
template <typename Fn>
void update_v(int u, int v, const Fn f) const;
頂点 $u, v$ 間の頂点に対して $f$ を基に更新する。
template <typename F, typename G, typename T>
T query_v(int u, int v, const F f, const G g, const T id_t) const;
頂点 $u, v$ 間の頂点に対する $f$ を基に $g$ でまとめたクエリの解
template <typename Fn>
void update_subtree_v(const int ver, const Fn f) const;
頂点 $\mathrm{ver}$ の部分木の頂点に対して $f$ を基に更新する。
template <typename T, typename Fn>
T query_subtree_v(const int ver, const Fn f) const;
頂点 $\mathrm{ver}$ の部分木の頂点に対する $f$ を基にしたクエリの解
template <typename Fn>
void update_e(int u, int v, const Fn f) const;
頂点 $u, v$ 間の辺に対して $f$ を基に更新する。
template <typename F, typename G, typename T>
T query_e(int u, int v, const F f, const G g, const T id_t) const;
頂点 $u, v$ 間の辺に対する $f$ を基に $g$ でまとめたクエリの解
template <typename Fn>
void update_subtree_e(const int ver, const Fn f) const;
頂点 $\mathrm{ver}$ の部分木の辺に対して $f$ を基に更新する。
template <typename T, typename Fn>
T query_subtree_e(const int ver, const Fn f) const;
頂点 $\mathrm{ver}$ の部分木の辺に対する $f$ を基にしたクエリの解
int lowest_common_ancestor(int u, int v) const;
頂点 $u, v$ の最小共通祖先
参考文献
Daniel D. Sleator and Robert Endre Tarjan: A data structure for dynamic trees, Journal of Computer and System Sciences , Vol. 26, No. 3, pp. 362–391 (1983). https://doi.org/10.1016/0022-0000(83)90006-5
https://www.slideshare.net/hcpc_hokudai/study-20150107
http://beet-aizu.hatenablog.com/entry/2017/12/12/235950
https://github.com/beet-aizu/library/blob/627950ae389af108b3c3f431f057c58891b0ba72/tree/heavylightdecomposition.cpp
https://codeforces.com/blog/entry/53170
TODO
高速化
http://yosupo.hatenablog.com/entry/2015/10/02/233244
Submissons
https://onlinejudge.u-aizu.ac.jp/solutions/problem/2667/review/4084766/emthrm/C++14
Depends on
Verified with
Code
#ifndef EMTHRM_GRAPH_TREE_HEAVY_LIGHT_DECOMPOSITION_HPP_
#define EMTHRM_GRAPH_TREE_HEAVY_LIGHT_DECOMPOSITION_HPP_
#include <algorithm>
#include <utility>
#include <vector>
#include "emthrm/graph/edge.hpp"
namespace emthrm {
template < typename CostType >
struct HeavyLightDecomposition {
std :: vector < int > parent , subtree , id , inv , head ;
std :: vector < CostType > cost ;
explicit HeavyLightDecomposition (
const std :: vector < std :: vector < Edge < CostType >>>& graph ,
const int root = 0 )
: graph ( graph ) {
const int n = graph . size ();
parent . assign ( n , - 1 );
subtree . assign ( n , 1 );
dfs1 ( root );
id . resize ( n );
inv . resize ( n );
head . assign ( n , root );
int cur_id = 0 ;
dfs2 ( root , & cur_id );
}
template < typename Fn >
void update_v ( int u , int v , const Fn f ) const {
while ( true ) {
if ( id [ u ] > id [ v ]) std :: swap ( u , v );
f ( std :: max ( id [ head [ v ]], id [ u ]), id [ v ] + 1 );
if ( head [ u ] == head [ v ]) break ;
v = parent [ head [ v ]];
}
}
template < typename F , typename G , typename T >
T query_v ( int u , int v , const F f , const G g , const T id_t ) const {
T left = id_t , right = id_t ;
while ( true ) {
if ( id_t [ u ] > id_t [ v ]) {
std :: swap ( u , v );
std :: swap ( left , right );
}
left = g ( left , f ( std :: max ( id_t [ head [ v ]], id_t [ u ]), id_t [ v ] + 1 ));
if ( head [ u ] == head [ v ]) break ;
v = parent [ head [ v ]];
}
return g ( left , right );
}
template < typename Fn >
void update_subtree_v ( const int ver , const Fn f ) const {
f ( id [ ver ], id [ ver ] + subtree [ ver ]);
}
template < typename T , typename Fn >
T query_subtree_v ( const int ver , const Fn f ) const {
return f ( id [ ver ], id [ ver ] + subtree [ ver ]);
}
template < typename Fn >
void update_e ( int u , int v , const Fn f ) const {
while ( true ) {
if ( id [ u ] > id [ v ]) std :: swap ( u , v );
if ( head [ u ] == head [ v ]) {
f ( id [ u ], id [ v ]);
break ;
} else {
f ( id [ head [ v ]] - 1 , id [ v ]);
v = parent [ head [ v ]];
}
}
}
template < typename F , typename G , typename T >
T query_e ( int u , int v , const F f , const G g , const T id_t ) const {
T left = id_t , right = id_t ;
while ( true ) {
if ( id [ u ] > id [ v ]) {
std :: swap ( u , v );
std :: swap ( left , right );
}
if ( head [ u ] == head [ v ]) {
left = g ( left , f ( id [ u ], id [ v ]));
break ;
} else {
left = g ( left , f ( id [ head [ v ]] - 1 , id [ v ]));
v = parent [ head [ v ]];
}
}
return g ( left , right );
}
template < typename Fn >
void update_subtree_e ( const int ver , const Fn f ) const {
f ( id [ ver ], id [ ver ] + subtree [ ver ] - 1 );
}
template < typename T , typename Fn >
T query_subtree_e ( const int ver , const Fn f ) const {
return f ( id [ ver ], id [ ver ] + subtree [ ver ] - 1 );
}
int lowest_common_ancestor ( int u , int v ) const {
while ( true ) {
if ( id [ u ] > id [ v ]) std :: swap ( u , v );
if ( head [ u ] == head [ v ]) break ;
v = parent [ head [ v ]];
}
return u ;
}
private:
std :: vector < std :: vector < Edge < CostType >>> graph ;
void dfs1 ( const int ver ) {
for ( int i = 0 ; std :: cmp_less ( i , graph [ ver ]. size ()); ++ i ) {
Edge < CostType >& e = graph [ ver ][ i ];
if ( e . dst != parent [ ver ]) {
parent [ e . dst ] = ver ;
dfs1 ( e . dst );
subtree [ ver ] += subtree [ e . dst ];
if ( subtree [ e . dst ] > subtree [ graph [ ver ]. front (). dst ]) {
std :: swap ( e , graph [ ver ]. front ());
}
}
}
}
void dfs2 ( const int ver , int * cur_id ) {
id [ ver ] = ( * cur_id ) ++ ;
inv [ id [ ver ]] = ver ;
for ( const Edge < CostType >& e : graph [ ver ]) {
if ( e . dst != parent [ ver ]) {
head [ e . dst ] = ( e . dst == graph [ ver ]. front (). dst ? head [ ver ] : e . dst );
cost . emplace_back ( e . cost );
dfs2 ( e . dst , cur_id );
}
}
}
};
} // namespace emthrm
#endif // EMTHRM_GRAPH_TREE_HEAVY_LIGHT_DECOMPOSITION_HPP_
#line 1 "include/emthrm/graph/tree/heavy-light_decomposition.hpp"
#include <algorithm>
#include <utility>
#include <vector>
#line 1 "include/emthrm/graph/edge.hpp"
/**
* @title 辺
*/
#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_
#include <compare>
namespace emthrm {
template < typename CostType >
struct Edge {
CostType cost ;
int src , dst ;
explicit Edge ( const int src , const int dst , const CostType cost = 0 )
: cost ( cost ), src ( src ), dst ( dst ) {}
auto operator <=> ( const Edge & x ) const = default ;
};
} // namespace emthrm
#endif // EMTHRM_GRAPH_EDGE_HPP_
#line 9 "include/emthrm/graph/tree/heavy-light_decomposition.hpp"
namespace emthrm {
template < typename CostType >
struct HeavyLightDecomposition {
std :: vector < int > parent , subtree , id , inv , head ;
std :: vector < CostType > cost ;
explicit HeavyLightDecomposition (
const std :: vector < std :: vector < Edge < CostType >>>& graph ,
const int root = 0 )
: graph ( graph ) {
const int n = graph . size ();
parent . assign ( n , - 1 );
subtree . assign ( n , 1 );
dfs1 ( root );
id . resize ( n );
inv . resize ( n );
head . assign ( n , root );
int cur_id = 0 ;
dfs2 ( root , & cur_id );
}
template < typename Fn >
void update_v ( int u , int v , const Fn f ) const {
while ( true ) {
if ( id [ u ] > id [ v ]) std :: swap ( u , v );
f ( std :: max ( id [ head [ v ]], id [ u ]), id [ v ] + 1 );
if ( head [ u ] == head [ v ]) break ;
v = parent [ head [ v ]];
}
}
template < typename F , typename G , typename T >
T query_v ( int u , int v , const F f , const G g , const T id_t ) const {
T left = id_t , right = id_t ;
while ( true ) {
if ( id_t [ u ] > id_t [ v ]) {
std :: swap ( u , v );
std :: swap ( left , right );
}
left = g ( left , f ( std :: max ( id_t [ head [ v ]], id_t [ u ]), id_t [ v ] + 1 ));
if ( head [ u ] == head [ v ]) break ;
v = parent [ head [ v ]];
}
return g ( left , right );
}
template < typename Fn >
void update_subtree_v ( const int ver , const Fn f ) const {
f ( id [ ver ], id [ ver ] + subtree [ ver ]);
}
template < typename T , typename Fn >
T query_subtree_v ( const int ver , const Fn f ) const {
return f ( id [ ver ], id [ ver ] + subtree [ ver ]);
}
template < typename Fn >
void update_e ( int u , int v , const Fn f ) const {
while ( true ) {
if ( id [ u ] > id [ v ]) std :: swap ( u , v );
if ( head [ u ] == head [ v ]) {
f ( id [ u ], id [ v ]);
break ;
} else {
f ( id [ head [ v ]] - 1 , id [ v ]);
v = parent [ head [ v ]];
}
}
}
template < typename F , typename G , typename T >
T query_e ( int u , int v , const F f , const G g , const T id_t ) const {
T left = id_t , right = id_t ;
while ( true ) {
if ( id [ u ] > id [ v ]) {
std :: swap ( u , v );
std :: swap ( left , right );
}
if ( head [ u ] == head [ v ]) {
left = g ( left , f ( id [ u ], id [ v ]));
break ;
} else {
left = g ( left , f ( id [ head [ v ]] - 1 , id [ v ]));
v = parent [ head [ v ]];
}
}
return g ( left , right );
}
template < typename Fn >
void update_subtree_e ( const int ver , const Fn f ) const {
f ( id [ ver ], id [ ver ] + subtree [ ver ] - 1 );
}
template < typename T , typename Fn >
T query_subtree_e ( const int ver , const Fn f ) const {
return f ( id [ ver ], id [ ver ] + subtree [ ver ] - 1 );
}
int lowest_common_ancestor ( int u , int v ) const {
while ( true ) {
if ( id [ u ] > id [ v ]) std :: swap ( u , v );
if ( head [ u ] == head [ v ]) break ;
v = parent [ head [ v ]];
}
return u ;
}
private:
std :: vector < std :: vector < Edge < CostType >>> graph ;
void dfs1 ( const int ver ) {
for ( int i = 0 ; std :: cmp_less ( i , graph [ ver ]. size ()); ++ i ) {
Edge < CostType >& e = graph [ ver ][ i ];
if ( e . dst != parent [ ver ]) {
parent [ e . dst ] = ver ;
dfs1 ( e . dst );
subtree [ ver ] += subtree [ e . dst ];
if ( subtree [ e . dst ] > subtree [ graph [ ver ]. front (). dst ]) {
std :: swap ( e , graph [ ver ]. front ());
}
}
}
}
void dfs2 ( const int ver , int * cur_id ) {
id [ ver ] = ( * cur_id ) ++ ;
inv [ id [ ver ]] = ver ;
for ( const Edge < CostType >& e : graph [ ver ]) {
if ( e . dst != parent [ ver ]) {
head [ e . dst ] = ( e . dst == graph [ ver ]. front (). dst ? head [ ver ] : e . dst );
cost . emplace_back ( e . cost );
dfs2 ( e . dst , cur_id );
}
}
}
};
} // namespace emthrm
Back to top page