結果

問題 No.386 貪欲な領主
ユーザー beet
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 HERE
signed 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0