HL Decomposition
コードについての説明
HL 分解とは木上のパス(+部分木)についてのクエリに効率よく答えることのできるデータ構造である.
部分木のうち最も要素数の大きいものに heavy edge,
それ以外のものに light edge を貼って heavy edge でつながれた path の部分をまとめて管理することで実質木の高さが $\O (\log n)$ になる.
これだけ読んでも絶対にわからない(ごめんなさい)ので、こちらのブログを参考にしてください.
以下の実装は一般的な HL 分解とは異なり, heavy edge から順番に探索することで部分木についてのクエリにも同じセグ木を用いて高速に答えることができるようにしている.
詳しくはこちらのブログを参考にしてください.
時間計算量: 構築 $\O (n \log n)$, 部分木クエリ $\O (\log n)$, パスクエリ $\O (\log^2 n)$
コード
class HLdecomposition{
private:
int V;
vector<vector<int> > G;
vector<int> stsize, parent, pathtop, in, out;
int root;
void BuildStsize(int u, int p){
stsize[u] = 1, parent[u] = p;
for(int& v : G[u]){
if(v == p){
if(v == G[u].back()) break;
else swap(v, G[u].back());
}
BuildStsize(v, u);
stsize[u] += stsize[v];
if(stsize[v] > stsize[G[u][0]]){
swap(v, G[u][0]);
}
}
}
void BuildPath(int u, int p, int& tm){
in[u] = tm++;
for(int v : G[u]){
if(v == p) continue;
pathtop[v] = (v == G[u][0] ? pathtop[u] : v);
BuildPath(v, u, tm);
}
out[u] = tm;
}
public:
void add_edge(int u, int v){
G[u].push_back(v), G[v].push_back(u);
}
void build(int _root=0){
root = _root;
int tm = 0;
BuildStsize(root, -1);
pathtop[root] = root;
BuildPath(root, -1, tm);
}
//元の頂点のインデックスの配列上でのidを返す
inline int get(int a){
return in[a];
}
int lca(int a, int b){
int pa = pathtop[a], pb = pathtop[b];
while(pathtop[a] != pathtop[b]){
if(in[pa] > in[pb]){
a = parent[pa], pa = pathtop[a];
}else{
b = parent[pb], pb = pathtop[b];
}
}
if(in[a] > in[b]) swap(a, b);
return a;
}
void subtree_query(int a, const function< void(int, int) > &func){
func(in[a], out[a]);
}
// 例: hl.path_query(q, r, [&](int l, int r){ seg.range(l, r, s); })
// 例: hl.query(q, r, [&](int l, int r){ ans += seg.query(l, r); })
void path_query(int a, int b, const function< void(int, int) > &func){
int pa = pathtop[a], pb = pathtop[b];
while(pathtop[a] != pathtop[b]){
if(in[pa] > in[pb]){
func(in[pa], in[a] + 1);
a = parent[pa], pa = pathtop[a];
}else{
func(in[pb], in[b] + 1);
b = parent[pb], pb = pathtop[b];
}
}
if(in[a] > in[b]) swap(a, b);
func(in[a], in[b] + 1);
}
HLdecomposition(int node_size) : V(node_size), G(V), stsize(V, 0), parent(V, -1),
pathtop(V, -1), in(V, -1), out(V, -1){}
};