TOP > 木 HL分解
HL分解(Heavy-Light-Decomposition)
説明
木をHL分解する。
TODO: 説明
計算量
- 構築 $O(V)$
- クエリ $O(\log V)$
実装例
- HeavyLightDecomposition($g$):= 木 $g$ で初期化する。
- build():= 構築する。
- query($u$, $v$, $ti$, $q$, $f$, $edge$):= 頂点 $u$ と $v$ を通るパスに対する取得クエリを処理する。$ti$ は単位元, $q$ は列に対するクエリを返す演算で, $f$ は列とは列同士の演算結果をマージする演算である。$edge$ を true にした場合, 頂点クエリではなく辺クエリとして処理する。$q$ や $f$ は非可換演算でもよいが最後に $l, r$ をマージするときにどちらかを反転する必要があることに注意。
- add($u$, $v$, $q$, $edge$):= 頂点 $u$ と $v$ を通るパスに対する更新クエリを処理する。
- lca($u$, $v$):= 頂点 $u$ と $v$ の最小共通祖先を返す。
- la($v$, $k$):= 頂点 $v$ から頂点 $0$ 方向に $k$ 個だけ遡った頂点を返す。
template< typename G >
struct HeavyLightDecomposition {
G &g;
vector< int > sz, in, out, head, rev, par;
HeavyLightDecomposition(G &g) :
g(g), sz(g.size()), in(g.size()), out(g.size()), head(g.size()), rev(g.size()), par(g.size()) {}
void dfs_sz(int idx, int p) {
par[idx] = p;
sz[idx] = 1;
if(g[idx].size() && g[idx][0] == p) swap(g[idx][0], g[idx].back());
for(auto &to : g[idx]) {
if(to == p) continue;
dfs_sz(to, idx);
sz[idx] += sz[to];
if(sz[g[idx][0]] < sz[to]) swap(g[idx][0], to);
}
}
void dfs_hld(int idx, int par, int ×) {
in[idx] = times++;
rev[in[idx]] = idx;
for(auto &to : g[idx]) {
if(to == par) continue;
head[to] = (g[idx][0] == to ? head[idx] : to);
dfs_hld(to, idx, times);
}
out[idx] = times;
}
void build() {
dfs_sz(0, -1);
int t = 0;
dfs_hld(0, -1, t);
}
int la(int v, int k) {
while(1) {
int u = head[v];
if(in[v] - k >= in[u]) return rev[in[v] - k];
k -= in[v] - in[u] + 1;
v = par[u];
}
}
int lca(int u, int v) {
for(;; v = par[head[v]]) {
if(in[u] > in[v]) swap(u, v);
if(head[u] == head[v]) return u;
}
}
template< typename T, typename Q, typename F >
T query(int u, int v, const T &ti, const Q &q, const F &f, bool edge = false) {
T l = ti, r = ti;
for(;; v = par[head[v]]) {
if(in[u] > in[v]) swap(u, v), swap(l, r);
if(head[u] == head[v]) break;
l = f(q(in[head[v]], in[v] + 1), l);
}
return f(f(q(in[u] + edge, in[v] + 1), l), r);
// return {f(q(in[u] + edge, in[v] + 1), l), r};
}
template< typename Q >
void add(int u, int v, const Q &q, bool edge = false) {
for(;; v = par[head[v]]) {
if(in[u] > in[v]) swap(u, v);
if(head[u] == head[v]) break;
q(in[head[v]], in[v] + 1);
}
q(in[u] + edge, in[v] + 1);
}
};
検証
AOJ GRL_5_C LCA: Lowest Common Ancestor
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C"
#include "../../template/template.cpp"
#include "../../graph/template.cpp"
#include "../heavy-light-decomposition.cpp"
int main() {
int N, Q;
scanf("%d", &N);
UnWeightedGraph g(N);
HeavyLightDecomposition< UnWeightedGraph > tree(g);
for(int i = 0; i < N; i++) {
int k;
scanf("%d", &k);
for(int j = 0; j < k; j++) {
int c;
scanf("%d", &c);
g[i].push_back(c);
}
}
tree.build();
scanf("%d", &Q);
for(int i = 0; i < Q; i++) {
int u, v;
scanf("%d %d", &u, &v);
printf("%d\n", tree.lca(u, v));
}
}
using int64 = long long;
const int64 INF = 1LL << 55;
struct State {
int64 ans, all, left, right;
State() : ans(-INF), all(0), left(-INF), right(-INF) {}
State(int64 val, int length) {
all = val * length;
ans = left = right = (val > 0 ? all : val);
}
State operator+(const State &s) const {
State ret;
ret.ans = max({ans, s.ans, right + s.left});
ret.all = all + s.all;
ret.left = max(left, all + s.left);
ret.right = max(s.right, right + s.all);
return (ret);
}
};
struct SegmentTree {
vector< State > seg;
vector< int64 > lazy;
int sz;
SegmentTree(int n) {
sz = 1;
while(sz < n) sz <<= 1;
seg.assign(2 * sz - 1, State());
lazy.assign(2 * sz - 1, INF);
}
void push(int k, int l, int r) {
if(lazy[k] == INF) return;
seg[k] = State(lazy[k], r - l);
if(k < sz - 1) {
lazy[2 * k + 1] = lazy[k];
lazy[2 * k + 2] = lazy[k];
}
lazy[k] = INF;
}
void update(int a, int b, int x, int k, int l, int r) {
push(k, l, r);
if(a >= r || b <= l) {
return;
}
if(a <= l && r <= b) {
lazy[k] = x;
push(k, l, r);
return;
}
update(a, b, x, 2 * k + 1, l, (l + r) >> 1);
update(a, b, x, 2 * k + 2, (l + r) >> 1, r);
seg[k] = seg[2 * k + 1] + seg[2 * k + 2];
}
State query(int a, int b, int k, int l, int r) {
push(k, l, r);
if(a >= r || b <= l) return (State());
if(a <= l && r <= b) return (seg[k]);
return (query(a, b, 2 * k + 1, l, (l + r) >> 1) +
query(a, b, 2 * k + 2, (l + r) >> 1, r));
}
void update(int a, int b, int x) {
update(a, b, x, 0, 0, sz);
}
State query(int a, int b) {
return (query(a, b, 0, 0, sz));
}
void set(int k, int v) {
seg[k + sz - 1] = State(v, 1);
}
void build() {
for(int k = sz - 2; k >= 0; k--) {
seg[k] = seg[2 * k + 1] + seg[2 * k + 2];
}
}
};
int main() {
int N, Q, S[200000];
scanf("%d %d", &N, &Q);
for(int i = 0; i < N; i++) {
scanf("%d", &S[i]);
}
UnWeightedGraph g(N);
HeavyLightDecomposition< UnWeightedGraph > tree(g);
for(int i = 0; i < N - 1; i++) {
int u, v;
scanf("%d %d", &u, &v);
--u, --v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
tree.build();
SegmentTree seg(N);
for(int i = 0; i < N; i++) seg.set(i, S[tree.rev[i]]);
seg.build();
while(Q--) {
int T, A, B, C;
scanf("%d %d %d %d", &T, &A, &B, &C);
--A, --B;
if(T == 1) {
tree.add(A, B, [&](int a, int b) { seg.update(a, b, C); });
} else {
/* l と r をマージせずに返すように実装を変更している */
auto beet = tree.query(A, B, State(), [&](int a, int b) { return seg.query(a, b); }, [](const State &a, const State &b) { return a + b; });
swap(beet.first.left, beet.first.right);
printf("%lld\n", (beet.first + beet.second).ans);
}
}
}