HL分解で部分木クエリ
HL分解*1でパスクエリができることは知ってたけど同時に部分木クエリも行えることを知ったのでメモ. (もしかして割と常識なのかな？)
これ
https://codeforces.com/blog/entry/53170
弱い方のHL分解
元々持ってたライブラリでは, 一回 dfs で各部分木のサイズを求めてから heavy-edge *2を見つけて, その後 bfs で根に近い heavy-path から順に, その中でも根に近い頂点から順に番号を振る感じでやってました.
これで各 heavy-path 上の頂点は全て連続した番号を持つので, パスクエリには対処できます.
しかしこれだと部分木クエリをやりたくても一つの部分列にはならないので, たぶん無理です.
強い方のHL分解
一回目の dfs までは同じで, 次に番号を振るときに bfs ではなく dfs をします. (なので番号の順序は行きがけ順に変わります)
このとき, 各頂点で最初に必ず heavy-edge から潜るようにします.
そうすることで, 各 heavy-path 上の頂点がオイラーツアー上において一つの連続した部分列になるのでパスクエリができます.
さらに, オイラーツアーなので各部分木の頂点も連続な部分列になって部分木クエリも可能になります.
もちろん LCA とかも求められます.
実装例
class heavy_light_decomposition { const int n; vector<vector<int>> g; vector<int> in, out, size, head, par; int it; void erase_par(int v, int prev) { par[v] = prev; for (auto& u : g[v]) { if (u == g[v].back()) break; if (u == prev) swap(u, g[v].back()); erase_par(u, v); } g[v].pop_back(); } void dfs1(int v) { for (auto& u : g[v]) { dfs1(u); size[v] += size[u]; if (size[u] > size[g[v][0]]) swap(u, g[v][0]); } } void dfs2(int v) { in[v] = it++; for (auto u : g[v]) { head[u] = (u == g[v][0] ? head[v] : u); dfs2(u); } out[v] = it; } public: heavy_light_decomposition(int n_) : n(n_), g(n), in(n, -1), out(n, -1), size(n, 1), head(n), par(n, -1), it(0) {} heavy_light_decomposition(const vector<vector<int>>& G) : n(G.size()), g(G), in(n, -1), out(n, -1), size(n, 1), head(n), par(n, -1), it(0) {} void add_edge(int u, int v) { g[u].push_back(v); g[v].push_back(u); } void build(int rt = 0) { for (auto v : g[rt]) erase_par(v, rt); dfs1(rt); head[rt] = rt; dfs2(rt); } int get_id(int v) { return in[v]; } int get_lca(int u, int v) { while (true) { if (in[u] > in[v]) swap(u, v); if (head[u] == head[v]) return u; v = par[head[v]]; } } void path_query(int u, int v, function<void(int, int)> f) { while (true) { if (in[u] > in[v]) swap(u, v); f(max(in[head[v]], in[u]), in[v] + 1); if (head[u] == head[v]) return; v = par[head[v]]; } } void subtree_query(int v, function<void(int, int)> f) { f(in[v], out[v]); } };
パス/部分木クエリではラムダ式とかで f を渡して使います.
f には半開区間 [l, r) が渡されます.
ちなみに木のサイズが 1e6 とかの場合は, スタックオーバーフローする可能性が高いので再帰を展開した方が良いでしょう.
例題
このHL分解を使うと以下の問題が解けます.
Subtrees And Paths | HackerRank
問題概要
サイズN(<=1e5)の根付き木の各頂点が整数値を持っている. これらは全て初期値０. 以下のクエリをQ(<=1e5)個処理せよ.
- add t value : 頂点 t の部分木に含まれる任意の頂点の整数値に値 value を加算
- max a b : 頂点 a から頂点 b までのパスに含まれる任意の頂点が持つ整数値の最大値を出力
解法
区間加算とRMQ ができればよいので, Starry Sky Tree または遅延セグメントツリーと HL分解を組み合わせればよいです.
addクエリは O(logN), maxクエリは O( (logN)^2) でできます.
