結果
問題 | No.900 aδδitivee |
ユーザー | IKyopro |
提出日時 | 2019-12-23 23:30:13 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,764 bytes |
コンパイル時間 | 2,675 ms |
コンパイル使用メモリ | 219,528 KB |
実行使用メモリ | 26,184 KB |
最終ジャッジ日時 | 2024-09-19 04:09:59 |
合計ジャッジ時間 | 9,435 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
ソースコード
#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 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]+1,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]) 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; } } }