AOJ 0367: Charging System for Network/ネットワークの課金システム

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0367&lang=ja

解法

ネットワークはマシンを頂点としケーブルの太さを各辺の重みとする木と考えます。

add クエリが扱いにくいので、各頂点  v に対し整数  A _ v を辺  (v, w) の重みが常に  A _ v + A _ w となるようにすると、add クエリが  A _ x d を加えるというクエリになります。 A _ v の初期値は BFS をすることで計算できます。

send クエリは、頂点  s から頂点  t の最短路を  v _ 1, v _ 2, \cdots, v _ M \ (v _ 1 = s, v _ M = t) としたとき、 \displaystyle{\sum _ {i = 1} ^ {M - 1} f(A _ {v _ i} + A _ {v _ {i + 1}})} (ただし  f(n) n K の倍数のとき  0、そうでないとき  n) を求めることに帰着され、これは列  [B _ 1, B _ 2, \cdots, B _ M] の情報を  B _ 1, B _ M, \displaystyle{\sum _ {i = 1} ^ {M - 1} f(B _ i + B _ {i + 1})} の組として持つと、HLD にセグメント木を載せることで処理できます。

計算量は  O(N + Q(\log N) ^ 2) です。

実装

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=5956782

#include <bits/stdc++.h>
using namespace std;
struct monoid{
  bool e;
  long long L, R, S;
  monoid(): e(true){
  }
  monoid(long long x): e(false), L(x), R(x), S(0){
  }
};
monoid f(monoid A, monoid B, int K){
  if (A.e){
    return B;
  }
  if (B.e){
    return A;
  }
  monoid ans;
  ans.e = false;
  ans.L = A.L;
  ans.R = B.R;
  ans.S = A.S + B.S;
  if ((A.R + B.L) % K != 0){
    ans.S += A.R + B.L;
  }
  return ans;
};
struct segment_tree{
  int N;
  array<vector<monoid>, 2> ST;
  int K;
  segment_tree(){
  }
  segment_tree(vector<long long> &A, int K): K(K){
    int N2 = A.size();
    N = 1;
    while (N < N2){
      N *= 2;
    }
    ST[0] = vector<monoid>(N * 2 - 1);
    ST[1] = vector<monoid>(N * 2 - 1);
    for (int i = 0; i < N2; i++){
      ST[0][N - 1 + i] = monoid(A[i]);
      ST[1][N - 1 + i] = monoid(A[i]);
    }
    for (int i = N - 2; i >= 0; i--){
      ST[0][i] = f(ST[0][i * 2 + 1], ST[0][i * 2 + 2], K);
      ST[1][i] = f(ST[1][i * 2 + 2], ST[1][i * 2 + 1], K);
    }
  }
  void update(int i, int x){
    i += N - 1;
    ST[0][i].L += x;
    ST[0][i].R += x;
    ST[1][i].L += x;
    ST[1][i].R += x;
    while (i > 0){
      i = (i - 1) / 2;
      ST[0][i] = f(ST[0][i * 2 + 1], ST[0][i * 2 + 2], K);
      ST[1][i] = f(ST[1][i * 2 + 2], ST[1][i * 2 + 1], K);
    }
  }
  monoid range_fold(int L, int R, int d, int i, int l, int r){
    if (r <= L || R <= l){
      return monoid();
    } else if (L <= l && r <= R){
      return ST[d][i];
    } else {
      int m = (l + r) / 2;
      if (d == 0){
        return f(range_fold(L, R, d, i * 2 + 1, l, m), range_fold(L, R, d, i * 2 + 2, m, r), K);
      } else {
        return f(range_fold(L, R, d, i * 2 + 2, m, r), range_fold(L, R, d, i * 2 + 1, l, m), K);
      }
    }
  }
  monoid range_fold(int L, int R, int d){
    return range_fold(L, R, d, 0, 0, N);
  }
};
struct heavy_light_decomposition{
  vector<int> p, sz, in, next;
  segment_tree ST;
  int K;
  heavy_light_decomposition(vector<int> &p, vector<vector<int>> &c, vector<long long> &A, int K): p(p), K(K){
    int N = p.size();
    sz = vector<int>(N, 1);
    dfs1(c);
    in = vector<int>(N);
    next = vector<int>(N);
    next[0] = 0;
    int t = 0;
    dfs2(c, t);
    vector<long long> A2(N);
    for (int i = 0; i < N; i++){
      A2[in[i]] = A[i];
    }
    ST = segment_tree(A2, K);
  }
  void dfs1(vector<vector<int>> &c, int v = 0){
    for (int &w : c[v]){
      dfs1(c, w);
      sz[v] += sz[w];
      if (sz[w] > sz[c[v][0]]){
        swap(w, c[v][0]);
      }
    }
  }
  void dfs2(vector<vector<int>> &c, int &t, int v = 0){
    in[v] = t;
    t++;
    for (int w : c[v]){
      if (w == c[v][0]){
        next[w] = next[v];
      } else {
        next[w] = w;
      }
      dfs2(c, t, w);
    }
  }
  void update(int v, int x){
    ST.update(in[v], x);
  }
  int lca(int u, int v){
    while (true){
      if (in[u] > in[v]){
        swap(u, v);
      }
      if (next[u] == next[v]){
        return u;
      }
      v = p[next[v]];
    }
  }
  monoid path_fold(int u, int v){
    int w = lca(u, v);
    monoid L;
    while (next[u] != next[w]){
      L = f(L, ST.range_fold(in[next[u]], in[u] + 1, 1), K);
      u = p[next[u]];
    }
    L = f(L, ST.range_fold(in[w], in[u] + 1, 1), K);
    monoid R;
    while (next[v] != next[w]){
      R = f(ST.range_fold(in[next[v]], in[v] + 1, 0), R, K);
      v = p[next[v]];
    }
    R = f(ST.range_fold(in[w] + 1, in[v] + 1, 0), R, K);
    return f(L, R, K);
  }
};
int main(){
  int N, K;
  cin >> N >> K;
  vector<vector<pair<int, int>>> E(N);
  for (int i = 0; i < N - 1; i++){
    int a, b, c;
    cin >> a >> b >> c;
    E[a].push_back(make_pair(c, b));
    E[b].push_back(make_pair(c, a));
  }
  vector<int> p(N, -1);
  vector<vector<int>> c(N);
  vector<long long> a(N);
  a[0] = 0;
  queue<int> q;
  q.push(0);
  while (!q.empty()){
    int v = q.front();
    q.pop();
    for (auto P : E[v]){
      int w = P.second;
      if (w != p[v]){
        p[w] = v;
        c[v].push_back(w);
        a[w] = P.first - a[v];
        q.push(w);
      }
    }
  }
  heavy_light_decomposition T(p, c, a, K);  
  int Q;
  cin >> Q;
  for (int i = 0; i < Q; i++){
    string S;
    cin >> S;
    if (S == "add"){
      int x, d;
      cin >> x >> d;
      T.update(x, d);
    }
    if (S == "send"){
      int s, t;
      cin >> s >> t;
      cout << T.path_fold(s, t).S << endl;
    }
  }
}