結果
問題 | No.386 貪欲な領主 |
ユーザー |
![]() |
提出日時 | 2019-03-03 17:50:09 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 196 ms / 2,000 ms |
コード長 | 4,153 bytes |
コンパイル時間 | 2,238 ms |
コンパイル使用メモリ | 206,540 KB |
最終ジャッジ日時 | 2025-01-06 21:54:51 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include<bits/stdc++.h>using namespace std;using Int = long long;template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}struct HLDecomposition {Int n,pos;vector<vector<Int> > G;vector<Int> vid, head, sub, par, dep, inv, type;HLDecomposition(){}HLDecomposition(Int n):n(n),pos(0),G(n),vid(n,-1),head(n),sub(n,1),par(n,-1),dep(n,0),inv(n),type(n){}void add_edge(Int u, Int v) {G[u].push_back(v);G[v].push_back(u);}void build(vector<Int> rs={0}) {Int c=0;for(Int r:rs){dfs_sz(r);head[r]=r;dfs_hld(r,c++);}}void dfs_sz(Int v) {for(Int &u:G[v]){if(u==par[v]) continue;par[u]=v;dep[u]=dep[v]+1;dfs_sz(u);sub[v]+=sub[u];if(sub[u]>sub[G[v][0]]) swap(u,G[v][0]);}}void dfs_hld(Int v,Int c) {vid[v]=pos++;inv[vid[v]]=v;type[v]=c;for(Int u:G[v]){if(u==par[v]) continue;head[u]=(u==G[v][0]?head[v]:u);dfs_hld(u,c);}}// for_each(vertex)// [l,r] <- attention!!template<typename F>void for_each(Int u, Int v, const F& f) {while(1){if(vid[u]>vid[v]) swap(u,v);f(max(vid[head[v]],vid[u]),vid[v]);if(head[u]!=head[v]) v=par[head[v]];else break;}}template<typename T,typename Q,typename F>T for_each(Int u,Int v,T ti,const Q &q,const F &f){T l=ti,r=ti;while(1){if(vid[u]>vid[v]){swap(u,v);swap(l,r);}l=f(l,q(max(vid[head[v]],vid[u]),vid[v]));if(head[u]!=head[v]) v=par[head[v]];else break;}return f(l,r);}// for_each(edge)// [l,r] <- attention!!template<typename F>void for_each_edge(Int u, Int v,const F& f) {while(1){if(vid[u]>vid[v]) swap(u,v);if(head[u]!=head[v]){f(vid[head[v]],vid[v]);v=par[head[v]];}else{if(u!=v) f(vid[u]+1,vid[v]);break;}}}Int lca(Int u,Int v){while(1){if(vid[u]>vid[v]) swap(u,v);if(head[u]==head[v]) return u;v=par[head[v]];}}Int distance(Int u,Int v){return dep[u]+dep[v]-2*dep[lca(u,v)];}};template <typename T>struct SegmentTree{using F = function<T(T,T)>;Int n;F f;T ti;vector<T> dat;SegmentTree(){};SegmentTree(F f,T ti):f(f),ti(ti){}void init(Int n_){n=1;while(n<n_) n<<=1;dat.assign(n<<1,ti);}void build(const vector<T> &v){Int n_=v.size();init(n_);for(Int i=0;i<n_;i++) dat[n+i]=v[i];for(Int i=n-1;i;i--)dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);}void set_val(Int k,T x){dat[k+=n]=x;while(k>>=1)dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);}T query(Int a,Int b){T vl=ti,vr=ti;for(Int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {if(l&1) vl=f(vl,dat[l++]);if(r&1) vr=f(dat[--r],vr);}return f(vl,vr);}template<typename C>Int find(Int a,Int b,C &check,Int k,Int l,Int r){if(!check(dat[k])||r<=a||b<=l) return -1;if(k>=n) return k-n;Int m=(l+r)>>1;Int vl=find(a,b,check,(k<<1)|0,l,m);if(~vl) return vl;return find(a,b,check,(k<<1)|1,m,r);}template<typename C>Int find(Int a,Int b,C &check){return find(a,b,check,1,0,n);}};struct FastIO{FastIO(){cin.tie(0);ios::sync_with_stdio(0);}}fastio_beet;//INSERT ABOVE HEREsigned main(){Int n;cin>>n;HLDecomposition hld(n);for(Int i=1;i<n;i++){Int x,y;cin>>x>>y;hld.add_edge(x,y);}hld.build();vector<Int> vs(n);for(Int i=0;i<n;i++) cin>>vs[i];auto f=[](Int a,Int b){return a+b;};SegmentTree<Int> seg(f,0);vector<Int> ts(n);for(Int i=0;i<n;i++) ts[hld.vid[i]]=vs[i];seg.build(ts);Int m;cin>>m;Int res=0;for(Int i=0;i<m;i++){Int a,b,c;cin>>a>>b>>c;auto calc=[&](Int l,Int r){res+=seg.query(l,r+1)*c;};hld.for_each(a,b,calc);}cout<<res<<endl;return 0;}