結果

問題 No.900 aδδitivee
ユーザー kappybar
提出日時 2020-07-16 17:30:34
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 299 ms / 2,000 ms
コード長 3,525 bytes
コンパイル時間 2,076 ms
コンパイル使用メモリ 185,008 KB
実行使用メモリ 31,300 KB
最終ジャッジ日時 2024-11-25 00:57:54
合計ジャッジ時間 11,522 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
using ll = long long ;
using P = pair<int,int> ;
using pll = pair<long long,long long>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e17;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;


template<typename Mono,typename Ope>
struct LazySegmentTree{
    using F = function<Mono(Mono,Mono)>;
    using G = function<Mono(Mono,Ope)>;
    using H = function<Ope(Ope,Ope)>;
    int n,height;
    F f; G g; H h; Mono tu; Ope eu;
    vector<Mono> node;
    vector<Ope> lazy;

    LazySegmentTree(F f,G g,H h,Mono tu,Ope eu):f(f),g(g),h(h),tu(tu),eu(eu){}

    void init(vector<Mono> v){
        int n_ = (int)(v.size());
        n = 1;height = 0;
        while(n < n_) n <<= 1,++ height;
        node.assign(2*n,tu);
        lazy.assign(2*n,eu);
        for(int i=0;i<n_;i++) node[i+n] = v[i];
        for(int i=n-1;i>0;i--) node[i] = f(node[i<<1],node[i<<1|1]);
    }

    Mono eval(int k){
        return (lazy[k]==eu)?node[k]:g(node[k],lazy[k]);
    }

    void prop(int k){
        if(lazy[k]==eu) return;
        lazy[k<<1] = h(lazy[k<<1],lazy[k]);
        lazy[k<<1|1] = h(lazy[k<<1|1],lazy[k]);
        node[k] = eval(k);
        lazy[k] = eu;
    }

    void prop_above(int k){
        for(int i=height;i>0;i--) prop(k>>i);
    }

    void recalc_above(int k){
        while(k>0){
            k >>= 1;
            node[k] = f(eval(k<<1),eval(k<<1|1));
        }
    }

    void set_val(int k,Mono x){
        k += n;
        prop_above(k);
        node[k] = x;
        lazy[k] = eu;
        recalc_above(k);
    }

    void update(int l,int r,Ope x){
        if(l >= r) return;
        l += n;r += n-1;
        prop_above(l);
        prop_above(r);
        int a = l,b = r;
        ++ r;
        while(l < r){
            if(l&1) lazy[l] = h(lazy[l],x), ++l;
            if(r&1) --r, lazy[r] = h(lazy[r],x);
            l >>= 1;r >>= 1;
        }
        recalc_above(a);
        recalc_above(b);
    }

    Mono query(int l,int r){
        if(l >= r) return tu;
        l += n;r += n-1;
        prop_above(l);
        prop_above(r);++r;
        Mono vl = tu,vr = tu;
        while(l < r){
            if(l&1) vl = f(vl,eval(l)), ++l;
            if(r&1) --r, vr = f(eval(r),vr);
            l >>= 1;r >>= 1;
        }
        return f(vl,vr);
    }
};
int n = 100005;
vector<pll> vv(2*n,pll(0,0));
vector<int> l(n);
vector<int> r(n);
vector<vector<pll>> tree(n,vector<pll>());
int idx=1;

void dfs(int i,int &idx){
    l[i] = idx;
    for(pll v:tree[i]){
        vv[idx++] = pll(v.first,1);
        dfs(v.second,idx);
        vv[idx++] = pll(-v.first,-1);
    }
    r[i] = idx;
}

int main(){
    auto f = [](pll a,pll b){
        a.first+=b.first;
        a.second+=b.second;
        return a;
    };
    auto g = [](pll a,ll b){
        a.first += b*a.second;
        return a;
    };
    auto h = [](ll a,ll b){
        return a+b;
    };
    LazySegmentTree<pll,ll> seg(f,g,h,pll(0,0),0);

    cin >> n;
    rep(i,n-1){
        int u,v;
        ll w;
        cin >> u >> v >> w;
        tree[u].push_back(pll(w,v));
    }

    dfs(0,idx);
    seg.init(vv);

    int q;
    cin >> q;
    while(q--){
        int t;
        cin >> t;
        if(t==1){
            int a;
            ll x;
            cin >> a >> x;
            seg.update(l[a],r[a],x);
        }else{
            int b;
            cin >> b;
            cout << seg.query(0,r[b]).first << endl;
        }
    }
    return 0;
}
0