結果
問題 | No.900 aδδitivee |
ユーザー |
|
提出日時 | 2024-03-21 01:01:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 512 ms / 2,000 ms |
コード長 | 13,149 bytes |
コンパイル時間 | 3,122 ms |
コンパイル使用メモリ | 221,560 KB |
最終ジャッジ日時 | 2025-02-20 10:22:30 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 |
ソースコード
#include <bits/stdc++.h>using namespace std;class HeavyLightDecomposition{protected:int V;vector<vector<int>> G;vector<int> stsize, parent, pathtop, depth, in, reverse_in, out;int root;private:// Subtree Sizevoid buildStsize(int curr, int prev){stsize[curr] = 1, parent[curr] = prev;for(int &v : G[curr]){if(v == prev){if(v == G[curr].back()) break;else swap(v, G[curr].back());}buildStsize(v, curr);stsize[curr] += stsize[v];if(stsize[v] > stsize[G[curr][0]]){swap(v, G[curr][0]);}}}void buildPath(int curr, int prev, int &t){in[curr] = t++;reverse_in[in[curr]] = curr;for(int v : G[curr]){if(v == prev) continue;if(v == G[curr][0]){pathtop[v] = pathtop[curr];} else{pathtop[v] = v;}depth[v] = depth[curr] + 1;buildPath(v, curr, t);}out[curr] = t;}public:HeavyLightDecomposition(int node_size) : V(node_size), G(V), stsize(V, 0), parent(V, -1),pathtop(V, -1), depth(V, 0), in(V, -1), reverse_in(V, -1), out(V, -1){}void add_edge(int u, int v){G[u].push_back(v);G[v].push_back(u);}void build(int _root = 0){root = _root;int t = 0;buildStsize(root, -1);pathtop[root] = root;buildPath(root, -1, t);}inline int get(int a){return in[a];}int la(int a, int k) {while(true){int u = pathtop[a];if(in[a] - k >= in[u]) return reverse_in[in[a] - k];k -= in[a] - in[u] + 1;a = parent[u];}}int lca(int a, int b){int pa = pathtop[a], pb = pathtop[b];while(pathtop[a] != pathtop[b]){if(in[pa] > in[pb]){a = parent[pa], pa = pathtop[a];} else{b = parent[pb], pb = pathtop[b];}}if(in[a] > in[b]) swap(a, b);return a;}int dist(int a, int b){ return depth[a] + depth[b] - 2 * depth[lca(a, b)]; }int jump(int from, int to, int k) {if(!k) return from;int l = lca(from, to);int d = dist(from, to);if(d < k) return -1;if(depth[from] - depth[l] >= k) return la(from, k);k -= depth[from] - depth[l];return la(to, depth[to] - depth[l] - k);}void subtree_query(int a, const function<void(int, int)> &func){func(in[a], out[a]);}void path_query(int a, int b, const function<void(int, int)> &func, bool include_root = true, bool reverse_path = false){vector<pair<int, int>> path;int pa = pathtop[a], pb = pathtop[b];while(pathtop[a] != pathtop[b]){if(in[pa] > in[pb]){path.emplace_back(in[pa], in[a] + 1);a = parent[pa], pa = pathtop[a];} else{path.emplace_back(in[pb], in[b] + 1);b = parent[pb], pb = pathtop[b];}}if(in[a] > in[b]) swap(a, b);if(include_root) path.emplace_back(in[a], in[b] + 1);else path.emplace_back(in[a] + 1, in[b] + 1);if(!reverse_path) reverse(path.begin(), path.end());else for(auto &p : path) p = make_pair(V - p.second, V - p.first);for(auto [u, v] : path){func(u, v);}}void path_noncommutative_query(int a, int b, const function<void(int, int)> &func, const function<void(int, int)> &func2){int l = lca(a, b);path_query(a, l, func2, false, true);path_query(l, b, func, true, false);}};template<typename T, T INF>struct SegmentTreeBeats{int n, n0;vector<T> max_v, smax_v, max_c;vector<T> min_v, smin_v, min_c;vector<T> sum;vector<T> len, ladd, lval;void update_node_max(int k, T x) {sum[k] += (x - max_v[k]) * max_c[k];if(max_v[k] == min_v[k]){max_v[k] = min_v[k] = x;}else if(max_v[k] == smin_v[k]){max_v[k] = smin_v[k] = x;}else{max_v[k] = x;}if(lval[k] != INF && x < lval[k]){lval[k] = x;}}void update_node_min(int k, T x) {sum[k] += (x - min_v[k]) * min_c[k];if(max_v[k] == min_v[k]){max_v[k] = min_v[k] = x;}else if(smax_v[k] == min_v[k]){min_v[k] = smax_v[k] = x;}else{min_v[k] = x;}if(lval[k] != INF && lval[k] < x){lval[k] = x;}}void push(int k){if(n0 - 1 <= k) return;if(lval[k] != INF){updateall(2 * k + 1, lval[k]);updateall(2 * k + 2, lval[k]);lval[k] = INF;return;}if(ladd[k] != 0){addall(2 * k + 1, ladd[k]);addall(2 * k + 2, ladd[k]);ladd[k] = 0;}if(max_v[k] < max_v[2 * k + 1]){update_node_max(2 * k + 1, max_v[k]);}if(min_v[2 * k + 1] < min_v[k]){update_node_min(2 * k + 1, min_v[k]);}if(max_v[k] < max_v[2 * k + 2]){update_node_max(2 * k + 2, max_v[k]);}if(min_v[2 * k + 2] < min_v[k]){update_node_min(2 * k + 2, min_v[k]);}}void update(int k){sum[k] = sum[2 * k + 1] + sum[2 * k + 2];if(max_v[2 * k + 1] < max_v[2 * k + 2]){max_v[k] = max_v[2 * k + 2];max_c[k] = max_c[2 * k + 2];smax_v[k] = max(max_v[2 * k + 1], smax_v[2 * k + 2]);}else if(max_v[2 * k + 1] > max_v[2 * k + 2]){max_v[k] = max_v[2 * k + 1];max_c[k] = max_c[2 * k + 1];smax_v[k] = max(smax_v[2 * k + 1], max_v[2 * k + 2]);}else{max_v[k] = max_v[2 * k + 1];max_c[k] = max_c[2 * k + 1] + max_c[2 * k + 2];smax_v[k] = max(smax_v[2 * k + 1], smax_v[2 * k + 2]);}if(min_v[2 * k + 1] < min_v[2 * k + 2]){min_v[k] = min_v[2 * k + 1];min_c[k] = min_c[2 * k + 1];smin_v[k] = min(smin_v[2 * k + 1], min_v[2 * k + 2]);}else if(min_v[2 * k + 1] > min_v[2 * k + 2]){min_v[k] = min_v[2 * k + 2];min_c[k] = min_c[2 * k + 2];smin_v[k] = min(min_v[2 * k + 1], smin_v[2 * k + 2]);}else{min_v[k] = min_v[2 * k + 1];min_c[k] = min_c[2 * k + 1] + min_c[2 * k + 2];smin_v[k] = min(smin_v[2 * k + 1], smin_v[2 * k + 2]);}}void _query_chmin(T x, int a, int b, int k, int l, int r) {if(b <= l || r <= a || max_v[k] <= x){return;}if(a <= l && r <= b && smax_v[k] < x){update_node_max(k, x);return;}push(k);_query_chmin(x, a, b, 2 * k + 1, l, (l + r) / 2);_query_chmin(x, a, b, 2 * k + 2, (l + r) / 2, r);update(k);}void _query_chmax(T x, int a, int b, int k, int l, int r) {if(b <= l || r <= a || x <= min_v[k]){return;}if(a <= l && r <= b && x < smin_v[k]){update_node_min(k, x);return;}push(k);_query_chmax(x, a, b, 2 * k + 1, l, (l + r) / 2);_query_chmax(x, a, b, 2 * k + 2, (l + r) / 2, r);update(k);}void addall(int k, T x) {max_v[k] += x;if(smax_v[k] != -INF) smax_v[k] += x;min_v[k] += x;if(smin_v[k] != INF) smin_v[k] += x;sum[k] += len[k] * x;if(lval[k] != INF){lval[k] += x;}else{ladd[k] += x;}}void updateall(int k, T x) {max_v[k] = x; smax_v[k] = -INF;min_v[k] = x; smin_v[k] = INF;max_c[k] = min_c[k] = len[k];sum[k] = x * len[k];lval[k] = x; ladd[k] = 0;}void _query_add(T x, int a, int b, int k, int l, int r) {if(b <= l || r <= a){return;}if(a <= l && r <= b){addall(k, x);return;}push(k);_query_add(x, a, b, 2 * k + 1, l, (l + r) / 2);_query_add(x, a, b, 2 * k + 2, (l + r) / 2, r);update(k);}void _query_update(T x, int a, int b, int k, int l, int r) {if(b <= l || r <= a){return;}if(a <= l && r <= b){updateall(k, x);return;}push(k);_query_update(x, a, b, 2 * k + 1, l, (l + r) / 2);_query_update(x, a, b, 2 * k + 2, (l + r) / 2, r);update(k);}T _query_max(int a, int b, int k, int l, int r) {if(b <= l || r <= a){return -INF;}if(a <= l && r <= b){return max_v[k];}push(k);T lv = _query_max(a, b, 2 * k + 1, l, (l + r) / 2);T rv = _query_max(a, b, 2 * k + 2, (l + r) / 2, r);return max(lv, rv);}T _query_min(int a, int b, int k, int l, int r) {if(b <= l || r <= a){return INF;}if(a <= l && r <= b){return min_v[k];}push(k);T lv = _query_min(a, b, 2 * k + 1, l, (l + r) / 2);T rv = _query_min(a, b, 2 * k + 2, (l + r) / 2, r);return min(lv, rv);}T _query_sum(int a, int b, int k, int l, int r) {if(b <= l || r <= a){return 0;}if(a <= l && r <= b){return sum[k];}push(k);T lv = _query_sum(a, b, 2 * k + 1, l, (l + r) / 2);T rv = _query_sum(a, b, 2 * k + 2, (l + r) / 2, r);return lv + rv;}public:SegmentTreeBeats(int n) : n(n){vector<T> a;init(n, a);}SegmentTreeBeats(int n, vector<T> &a) : n(n){init(n, a);}void init(int n, vector<T> &a){max_v.assign(4 * n, 0), smax_v.assign(4 * n, 0), max_c.assign(4 * n, 0);min_v.assign(4 * n, 0), smin_v.assign(4 * n, 0), min_c.assign(4 * n, 0);sum.assign(4 * n, 0);len.assign(4 * n, 0), ladd.assign(4 * n, 0); lval.assign(4 * n, 0);n0 = 1;while(n0 < n) n0 <<= 1;for(int i = 0; i < 2 * n0; ++i) ladd[i] = 0, lval[i] = INF;len[0] = n0;for(int i = 0; i < n0 - 1; ++i) len[2 * i + 1] = len[2 * i + 2] = (len[i] >> 1);for(int i = 0; i < n; ++i){max_v[n0 - 1 + i] = min_v[n0 - 1 + i] = sum[n0 - 1 + i] = (!a.empty() ? a[i] : 0);smax_v[n0 - 1 + i] = -INF;smin_v[n0 - 1 + i] = INF;max_c[n0 - 1 + i] = min_c[n0 - 1 + i] = 1;}for(int i = n; i < n0; ++i){max_v[n0 - 1 + i] = smax_v[n0 - 1 + i] = -INF;min_v[n0 - 1 + i] = smin_v[n0 - 1 + i] = INF;max_c[n0 - 1 + i] = min_c[n0 - 1 + i] = 0;}for(int i = n0 - 2; i >= 0; --i){update(i);}}// range minimize queryvoid query_chmin(int a, int b, T x){_query_chmin(x, a, b, 0, 0, n0);}// range maximize queryvoid query_chmax(int a, int b, T x){_query_chmax(x, a, b, 0, 0, n0);}// range add queryvoid query_add(int a, int b, T x){_query_add(x, a, b, 0, 0, n0);}// range update queryvoid query_update(int a, int b, T x){_query_update(x, a, b, 0, 0, n0);}// range minimum queryT query_max(int a, int b){return _query_max(a, b, 0, 0, n0);}// range maximum queryT query_min(int a, int b){return _query_min(a, b, 0, 0, n0);}// range sum queryT query_sum(int a, int b){return _query_sum(a, b, 0, 0, n0);}T get(int x){return _query_sum(x, x + 1, 0, 0, n0);}};int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n; cin >> n;HeavyLightDecomposition G(n);vector<int> u(n - 1), v(n - 1), w(n - 1);for(int i = 0; i < n - 1; i++){cin >> u[i] >> v[i] >> w[i];G.add_edge(u[i], v[i]);}G.build();SegmentTreeBeats<long long, 1LL << 60> seg(n);for(int i = 0; i < n - 1; i++){int idx = max(G.get(u[i]), G.get(v[i]));seg.query_update(idx, idx + 1, w[i]);}long long ans = 0;long long x;auto query1 = [&](int l, int r){seg.query_add(l + 1, r, x);};auto query2 = [&](int l, int r){ans += seg.query_sum(l, r);};int q; cin >> q;while(q--){int t; cin >> t;if(t == 1){int a; cin >> a >> x;G.subtree_query(a, query1);}else{int b; cin >> b;ans = 0;G.path_query(0, b, query2, false, false);cout << ans << "\n";}}}