結果
問題 | No.900 aδδitivee |
ユーザー |
|
提出日時 | 2019-09-16 21:45:06 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 298 ms / 2,000 ms |
コード長 | 3,619 bytes |
コンパイル時間 | 2,250 ms |
コンパイル使用メモリ | 186,068 KB |
実行使用メモリ | 37,496 KB |
最終ジャッジ日時 | 2024-10-03 05:31:52 |
合計ジャッジ時間 | 9,498 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 |
ソースコード
#include <bits/stdc++.h>using namespace std;using i64 = long long;struct lazy_segment_tree {using T = i64;using L = i64;T t_ide() { return 0; }L l_ide() { return 0; }T ope(const T& a, const T& b) { return a + b; }L lazy_ope(const L& a, const L& b) { return a + b; }T effect(const T& t, const L& l, const i64 len) { return t + l * len; }i64 n;vector<T> node;vector<L> lazy;vector<bool> flag;vector<i64> llen;/* create lazy_segment_tree for sequence [t_ide; sz]A */lazy_segment_tree(vector<i64> init, vector<i64> sig) {n = 1;while(n < init.size()) n *= 2;node.assign(n * 2, t_ide());lazy.assign(n * 2, l_ide());flag.assign(n * 2, false);llen.assign(n * 2, 0);for(int i = 0;i < init.size();i++) node[i + n - 1] = init[i];for(int i = 0;i < init.size();i++) llen[i + n - 1] = sig[i];for(int i = n - 2;i >= 0;i--) node[i] = ope(node[2 * i + 1], node[2 * i + 2]);for(int i = n - 2;i >= 0;i--) llen[i] = llen[2 * i + 1] + llen[2 * i + 2];}void eval(i64 l, i64 r, i64 k) {if(flag[k]) {node[k] = effect(node[k], lazy[k], llen[k]);if(r - l > 1) {lazy[k * 2 + 1] = lazy_ope(lazy[k * 2 + 1], lazy[k]);flag[k * 2 + 1] = true;lazy[k * 2 + 2] = lazy_ope(lazy[k * 2 + 2], lazy[k]);flag[k * 2 + 2] = true;}flag[k] = false;lazy[k] = l_ide();}}/* for i in [a, b) effect(a[i], lx) */void update(i64 a, i64 b, L lx, i64 l = 0, i64 r = -1, i64 k = 0) {if(r < 0) r = n;eval(l, r, k);if(b <= l || r <= a) return;else if(a <= l && r <= b) {lazy[k] = lazy_ope(lazy[k], lx);flag[k] = true;eval(l, r, k);}else {update(a, b, lx, l, (l + r) / 2, k * 2 + 1);update(a, b, lx, (l + r) / 2, r, k * 2 + 2);node[k] =ope(node[k * 2 + 1], node[k * 2 + 2]);}}/* the sum of a[i] for i in [a, b) */T get(i64 a, i64 b, i64 l = 0, i64 r = -1, i64 k = 0) {if(r < 0) r = n;eval(l, r, k);if(b <= l || r <= a) return t_ide();else if(a <= l && r <= b) return node[k];else return ope(get(a, b, l, (l + r) / 2, k * 2 + 1), get(a, b, (l + r) / 2, r, k * 2 + 2));}};struct eulartour_path {vector<vector<pair<i64, i64>>> G;vector<i64> in, out;vector<i64> weight;vector<i64> sign;i64 cnt;eulartour_path(i64 n): G(n), in(n), out(n) {}void add_edge(i64 u, i64 v, i64 w) {G[u].push_back({ v, w });G[v].push_back({ u, w });}void dfs(i64 v, i64 f) {for(auto to: G[v]) {if(to.first == f) continue;weight.push_back(to.second);sign.push_back(1);in[to.first] = cnt;cnt++;dfs(to.first, v);weight.push_back(-to.second);sign.push_back(-1);out[to.first] = cnt;cnt++;}}i64 start_tour(i64 r) {weight.push_back(0); // dummysign.push_back(0);in[r] = 0;cnt = 1;dfs(r, -1);out[r] = cnt;weight.push_back(0); // dummysign.push_back(0);cnt++;return cnt;}};int main() {i64 N;cin >> N;eulartour_path eul(N);for(int i = 0;i < N - 1;i++) {i64 a, b, w;cin >> a >> b >> w;eul.add_edge(a, b, w);}eul.start_tour(0);lazy_segment_tree seg(eul.weight, eul.sign);i64 Q;cin >> Q;for(int q = 0; q < Q; q++) {i64 type;cin >> type;if(type == 1) {i64 v, x;cin >> v >> x;seg.update(eul.in[v] + 1, eul.out[v], x);}else {i64 v;cin >> v;cout << seg.get(0, eul.in[v] + 1) << endl;}}}