結果

問題 No.900 aδδitivee
ユーザー IKyoproIKyopro
提出日時 2019-12-23 23:39:05
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 251 ms / 2,000 ms
コード長 4,913 bytes
コンパイル時間 2,614 ms
コンパイル使用メモリ 219,164 KB
実行使用メモリ 25,936 KB
最終ジャッジ日時 2024-09-19 04:22:33
合計ジャッジ時間 10,144 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 251 ms
21,180 KB
testcase_08 AC 219 ms
21,152 KB
testcase_09 AC 218 ms
21,300 KB
testcase_10 AC 234 ms
21,040 KB
testcase_11 AC 224 ms
21,292 KB
testcase_12 AC 218 ms
21,168 KB
testcase_13 AC 230 ms
21,272 KB
testcase_14 AC 237 ms
21,280 KB
testcase_15 AC 227 ms
21,272 KB
testcase_16 AC 231 ms
21,300 KB
testcase_17 AC 229 ms
21,208 KB
testcase_18 AC 230 ms
21,228 KB
testcase_19 AC 235 ms
21,232 KB
testcase_20 AC 220 ms
21,288 KB
testcase_21 AC 213 ms
21,088 KB
testcase_22 AC 183 ms
25,880 KB
testcase_23 AC 182 ms
25,904 KB
testcase_24 AC 186 ms
25,928 KB
testcase_25 AC 187 ms
25,896 KB
testcase_26 AC 186 ms
25,784 KB
testcase_27 AC 189 ms
25,936 KB
testcase_28 AC 185 ms
25,892 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vec<T>>;

template<typename Monoid,typename OperatorMonoid,typename F,typename G,typename H>
struct LazySegmentTree {
	int sz,height;
	vec<Monoid> data;
	vec<OperatorMonoid> lazy;
	const F op;
	const G homo;
	const H comp;
  	const Monoid e;
	const OperatorMonoid Oe;

	LazySegmentTree(int n,const F op,const G homo,const H comp,
					const Monoid &e,const OperatorMonoid Oe)
		: op(op),homo(homo),comp(comp),e(e),Oe(Oe) {
		sz = 1;
		height = 0;
		while(sz<=n) sz <<= 1,height++;
		data.assign(2*sz,e);
		lazy.assign(2*sz,Oe);
	}

	void set(int k,const Monoid &x) {
		data[k+sz] = x;
	}

	void build() {
		for(int k=sz-1;k>0;k--) {
			data[k] = op(data[2*k], data[2*k+1]);
		}
	}

	inline void propagate(int k) {
		if(lazy[k]!=Oe) {
			lazy[2*k] = comp(lazy[2*k], lazy[k]);
			lazy[2*k+1] = comp(lazy[2*k+1], lazy[k]);
			data[k] = reflect(k);
			lazy[k] = Oe;
		}
	}

	inline Monoid reflect(int k) {
		return lazy[k] == Oe? data[k]:homo(data[k],lazy[k]);
	}

	inline void recalc(int k) {
		while(k>>=1) data[k] = op(reflect(2*k), reflect(2*k+1));
	}

	inline void thrust(int k) {
		for(int i=height;i>0;i--) propagate(k>>i);
	}

	void update(int a, int b, const OperatorMonoid &x) {
		thrust(a+=sz);
		thrust(b+=sz-1);
		for(int l=a,r=b+1;l<r;l>>=1,r>>=1) {
			if(l&1) lazy[l] = comp(lazy[l],x),++l;
			if(r&1) --r, lazy[r] = comp(lazy[r],x);
		}
		recalc(a);
		recalc(b);
	}

	Monoid query(int a, int b) {
		thrust(a+=sz);
		thrust(b+=sz-1);
		Monoid L = e, R = e;
		for(int l=a, r=b+1;l<r;l>>= 1,r>>=1) {
			if(l&1) L = op(L,reflect(l++));
			if(r&1) R = op(reflect(--r),R);
		}
		return op(L,R);
	}

	Monoid operator[](const int &k) {
		return query(k,k+1);
	}
};

struct edge{
    int to,id;
    ll dist;
    edge(int to,ll dist=1,int id=1):to(to),id(id),dist(dist){};
};

class HeavLightDecomposition{
private:
    vvec<edge> g;
    vec<int> sz,in,out,head,par;
    int pos;

    void dfs_sz(int cur,int p){
        sz[cur] = 1;
        par[cur] = p;
        for(auto& e:g[cur]) if(e.to!=p){
            dfs_sz(e.to,cur);
            sz[cur] += sz[e.to];
            if(sz[e.to]>sz[g[cur][0].to]) swap(e,g[cur][0]);
        }
    }

    void dfs_hld(int cur,int p){
        in[cur] = pos++;
        for(auto& e:g[cur]) if(e.to!=p){
            head[e.to] = (e.to==g[cur][0].to? head[cur]:e.to);
            dfs_hld(e.to,cur);
        }
        out[cur] = pos;
    }
public:
    HeavLightDecomposition(){}
    HeavLightDecomposition(int N,int root,vvec<edge> tree):
    g(tree),sz(N),in(N),out(N),head(N),par(N){
        pos = 0;
        dfs_sz(root,-1);
        dfs_hld(root,-1);
    }

    int getin(int v){return in[v];}
    int getout(int v){return out[v];}
    int lca(int u,int v){
        while(true){
            if(in[u]>in[v]) swap(u,v);
            if(head[u]==head[v]) return u;
            v = par[head[v]];
        }
    }

    template<class T,class G>
    void update(int v,const T& x,const G& g){
        g(in[v]+1,out[v],x);
    }

    template<class T,class F,class Q>
    T query(int u,int v,const T &e,const F& f,const Q& q,bool isedge=false){
        T l = e,r = e;
        while(true){
            if(in[u]>in[v]){
                swap(u,v); swap(l,r);
            }
            if(head[u]==head[v]) break;
            l = f(q(in[head[v]],in[v]+1),l);
            v = par[head[v]];
        }
        return f(f(q(in[u]+isedge,in[v]+1),l),r);
    }

};

int main(){
	cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vvec<edge> tree(N);
    for(int i=0;i<N-1;i++){
        int a,b;
        ll w;
        cin >> a >> b >> w;
        tree[a].push_back({b,w});
    }
    HeavLightDecomposition HLD(N,0,tree);
    struct state{
    	ll sum,len;
    };
    auto op = [](state L,state R){
        return (state){L.sum+R.sum,L.len+R.len};
    };
    auto homo = [](state S,ll x){
        return (state){S.sum+x*S.len,S.len};
    };
    auto comp = [](ll a, ll b){return a+b;};
    state e = {0,0};
    LazySegmentTree<state,ll,decltype(op),decltype(homo),decltype(comp)>
    seg(N,op,homo,comp,(state){0,0},0);
    for(int i=0;i<N;i++){
        for(auto& e:tree[i]){
//            cerr << e.to << " " << HLD.getin(e.to) << " " << HLD.getout(e.to) << endl;
            seg.set(HLD.getin(e.to),(state) {e.dist,1});
        }

    }
    seg.build();
    
    int Q;
    cin >> Q;

    auto q = [&](int l,int r){return seg.query(l,r);};
    auto update = [&](int l,int r,ll x){seg.update(l,r,x);};
    for(int i=0;i<Q;i++){
        int t;
        cin >> t;
        if(t==1){
            int v; ll w;
            cin >> v >> w;
            HLD.update(v,w,update);
        }else{
            int v;
            cin >> v;
            state res = HLD.query(0,v,e,op,q,true);
            cout << res.sum << endl;
        }
    }
}
0