AOJ 0367: Charging System for Network/ネットワークの課金システム
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0367&lang=ja
解法
ネットワークはマシンを頂点としケーブルの太さを各辺の重みとする木と考えます。
add クエリが扱いにくいので、各頂点 に対し整数 を辺 の重みが常に となるようにすると、add クエリが に を加えるというクエリになります。 の初期値は BFS をすることで計算できます。
send クエリは、頂点 から頂点 の最短路を としたとき、 (ただし は が の倍数のとき 、そうでないとき ) を求めることに帰着され、これは列 ] の情報を の組として持つと、HLD にセグメント木を載せることで処理できます。
計算量は です。
実装
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; } } }