結果
問題 | No.900 aδδitivee |
ユーザー |
|
提出日時 | 2020-08-20 19:34:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 134 ms / 2,000 ms |
コード長 | 2,287 bytes |
コンパイル時間 | 3,355 ms |
コンパイル使用メモリ | 196,808 KB |
最終ジャッジ日時 | 2025-01-13 04:28:54 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 |
ソースコード
//#define _GLIBCXX_DEBUG#include <bits/stdc++.h>#define rep(i, n) for(int i=0; i<n; ++i)#define all(v) v.begin(), v.end()#define rall(v) v.rbegin(), v.rend()using namespace std;using ll = int64_t;using ld = long double;using P = pair<int, int>;using vs = vector<string>;using vi = vector<int>;using vvi = vector<vi>;template<class T> using PQ = priority_queue<T>;template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;const int INF = 0xccccccc;const ll LINF = 922337203685477580LL;template<typename T1, typename T2>inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}template<typename T1, typename T2>inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}template<typename T1, typename T2>istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}template<typename T1, typename T2>ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}struct edge {int to;int64_t cost;edge(int x=0, int64_t y=0):to(x), cost(y) {}};const int N = 1e5+10;//headint n;vector<edge> G[N];int q;int dist[N];P lr[N];ll info[N];ll bit[N][2];void add(int i, ll x, int w) {while(i <= n) {bit[i][w] += x;i += i&-i;}}ll sum(int i, int w) {ll res = 0;while(i) {res += bit[i][w];i &= i-1;}return res;}int dfs(int i, int &cnt1, ll npw) {int &res = lr[i].second;lr[i].first = cnt1++;info[i] = npw;for(edge &e:G[i]) {dist[e.to] = dist[i]+1;npw += e.cost;res += dfs(e.to, cnt1, npw);npw -= e.cost;}return ++res;}int main() {ios::sync_with_stdio(false);cin.tie(0);cin >> n;rep(i, n-1) {int a, b, w;cin >> a >> b >> w;G[a].emplace_back(b, w);}int c1 = 0;dfs(0, c1, 0);rep(i, n) {//cout << i << ' ' << info[i] << endl;int pl = lr[i].first;add(pl+1, info[i], 0);add(pl+2, -info[i], 0);}cin >> q;while(q--) {int type;cin >> type;if(type == 1) {int a, x;cin >> a >> x;add(lr[a].first+1, x, 1);add(lr[a].first+lr[a].second+1, -x, 1);add(lr[a].first+1, -(ll)x*dist[a], 0);add(lr[a].first+lr[a].second+1, (ll)x*dist[a], 0);}else {int b;cin >> b;cout << sum(lr[b].first+1, 0) + sum(lr[b].first+1, 1)*dist[b] << '\n';}}}