木の HL 分解
概要
木を分解してクエリを高速に処理したりするデータ構造です．ある頂点 $v$ の子たち $c_i$ について，それを根とする部分木の頂点数が最大のもののうち $1$ つを $c_h$ とおきます．このとき辺 $(v,c_h)$ は heavy，その他は light であると定義します． 全ての辺を heavy と light に分類すると，木は heavy からなるパス (下のコードでは chain) に分解でき，これを HL 分解 (Heavy-Light Decomposition) といいます．
ある頂点 $v$ を根とする部分木の頂点数を $s(v)$ と書きます．light で結ばれている子供の部分木は，それ以上の大きさの部分木を持つ子が他に存在するので $s(v)/2$ 以下になります． 根から葉まで移動するとき light を通る度にそれを根とする部分木の大きさが半分以下になっていくので， 根と葉の間にある light 辺と chain の数が log で抑えられます．
再帰なしで書いたらコードがすごく長くなってしまいました．
計算量
- 構築 $O(N)$
- chain を縮約した木の高さ $O(\log N)$
- chain の数 $O(N)$
- chain の長さ $O(N)$
使い方
hl_decomp hld(g)- グラフ
gから構築する．無向でも有向でも OK．多重辺はだめ． hld.parent[v]vの親の頂点．根なら -1hld.subsize[v]vを根とする部分木の頂点数hld.depth[v]vの根からの距離hld.head[v],hld.last[t]vが属する chain の先頭の頂点，末尾の頂点hld.prev[v],hld.next[v]vが属する chain での前の頂点，次の頂点．先頭，末尾なら -1hld.chain[v],hld.at[v]vが属する chain，その中での indexhld.chains- chain の列．head の深さの昇順に入っている
hld.climb(v)vが属する chain の先頭の親を返す．先頭が根なら -1hld.get_index(v)vが属する chain の番号と先頭からのインデックスのペアを返すhld.lca(u,v)u,vの LCA (最低共通先祖)
実装
struct hl_decomp {
const Graph &g;
int n;
std::vector<std::vector<int>> chains;
std::vector<int> parent, subsize, depth, head, last, next, prev, chain, at;
hl_decomp(const Graph &g_, int r = -1)
: g(g_),
n(g.size()),
chains(0),
parent(n, 0),
subsize(n, 0),
depth(n, -1),
head(n, 0),
last(n, 0),
next(n, -1),
prev(n, -1),
chain(n, -1),
at(n, 0) {
if (r != -1) decompose(r);
}
// u から根まで登りたいときは
// for(; u != -1; u = climb(u))
int climb(int v) const { return parent[head[v]]; }
// chains[first][second] = v
std::pair<int, int> get_index(int v) const { return std::make_pair(chain[v], at[v]); }
int size() const { return n; }
void decompose(const int root) {
static int stk[600010];
int k = 0;
stk[k++] = root;
parent[root] = -1;
depth[root] = 0;
while (k) {
int v = stk[--k];
if (v >= 0) {
stk[k++] = ~v;
for (auto &e : g[v]) {
int ch = e.dst;
if (depth[ch] == -1) {
depth[ch] = depth[v] + 1;
parent[ch] = v;
stk[k++] = ch;
}
}
} else {
int m = 0;
v = ~v;
subsize[v] = 1;
for (auto &e : g[v]) {
int ch = e.dst;
if (parent[v] == ch) continue;
subsize[v] += subsize[ch];
if (m < subsize[ch]) {
m = subsize[ch];
next[v] = ch;
}
}
}
}
k = 0;
stk[k++] = root;
while (k) {
int h = stk[--k];
for (auto &e : g[h]) {
if (parent[h] != e.dst) stk[k++] = e.dst;
}
if (chain[h] != -1) continue;
chains.push_back(std::vector<int>());
std::vector<int> &path = chains.back();
for (int cur = h; cur != -1;) {
path.push_back(cur);
cur = next[cur];
}
for (int i = 0; i < (int)path.size(); i++) {
int v = path[i];
head[v] = path.front();
last[v] = path.back();
next[v] = i + 1 != (int)path.size() ? path[i + 1] : -1;
prev[v] = i != 0 ? path[i - 1] : -1;
chain[v] = chains.size() - 1;
at[v] = i;
}
}
}
int lca(int u, int v) {
while (chain[u] != chain[v]) {
if (depth[head[u]] > depth[head[v]])
u = climb(u);
else
v = climb(v);
}
return depth[u] < depth[v] ? u : v;
}
};