結果

問題 No.900 aδδitivee
ユーザー niuezniuez
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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); // dummy
sign.push_back(0);
in[r] = 0;
cnt = 1;
dfs(r, -1);
out[r] = cnt;
weight.push_back(0); // dummy
sign.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;
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0