説明

木を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 &times) {
    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));
  }
}

AOJ 2450 Do use segment tree

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);
    }
  }
}