HLD 構造体

HL分解 解説:https://hcpc-hokudai.github.io/archive/graph_tree_001.pdf [詳解]

#include "hld.hpp"

公開メンバ関数
	HLD (int n)
void	add_edge (int a, int b)
void	build (int root=0)
	HLD (const vector< vector< int > > &g, int root=0)
vector< tuple< bool, int, int > >	path (int u, int v)
	頂点 u, v を結ぶパスをHL分解後の辺の列にして返す
int	lca (int u, int v)
	頂点 u, v のLCAを返す
int	at (int v)
	頂点vのHL分解後の列での位置を返す
pair< int, int >	subtree (int v)
	HL分解後の列で、頂点vの部分木に対応する区間を返す

詳解

HL分解 解説:https://hcpc-hokudai.github.io/archive/graph_tree_001.pdf

hld.hpp の 5 行目に定義があります。

構築子と解体子

HLD() [1/2]

HLD::HLD ( int n )

inline

hld.hpp の 6 行目に定義があります。

HLD() [2/2]

HLD::HLD ( const vector< vector< int > > & g, int root = 0 )

inline

hld.hpp の 9 行目に定義があります。

参照先 build().

関数詳解

add_edge()

void HLD::add_edge ( int a, int b )

inline

hld.hpp の 7 行目に定義があります。

build()

void HLD::build ( int root = 0 )

inline

hld.hpp の 8 行目に定義があります。

path()

vector< tuple< bool, int, int > > HLD::path ( int u, int v )

inline

頂点 u, v を結ぶパスをHL分解後の辺の列にして返す

[f, l, r] として、次を表す。

• [l, r]: HL分解後の頂点列
• f = true のとき、[l, r] はvからuへの向き
• そうでないとき、逆向き

hld.hpp の 23 行目に定義があります。

lca()

int HLD::lca ( int u, int v )

inline

頂点 u, v のLCAを返す

hld.hpp の 40 行目に定義があります。

at()

int HLD::at ( int v )

inline

頂点vのHL分解後の列での位置を返す

hld.hpp の 49 行目に定義があります。

subtree()

pair< int, int > HLD::subtree ( int v )

inline

HL分解後の列で、頂点vの部分木に対応する区間を返す

hld.hpp の 52 行目に定義があります。

---

この構造体詳解は次のファイルから抽出されました:

• graph/tree/hld.hpp