結果

問題 No.386 貪欲な領主
ユーザー beetbeet
提出日時 2019-03-03 17:50:09
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 197 ms / 2,000 ms
コード長 4,153 bytes
コンパイル時間 2,396 ms
コンパイル使用メモリ 210,636 KB
実行使用メモリ 23,576 KB
最終ジャッジ日時 2023-09-05 17:47:36
合計ジャッジ時間 4,574 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 146 ms
23,576 KB
testcase_05 AC 183 ms
18,360 KB
testcase_06 AC 192 ms
18,384 KB
testcase_07 AC 3 ms
4,376 KB
testcase_08 AC 26 ms
4,756 KB
testcase_09 AC 4 ms
4,376 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 6 ms
4,380 KB
testcase_14 AC 197 ms
18,292 KB
testcase_15 AC 122 ms
23,572 KB
権限があれば一括ダウンロードができます

ソースコード

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;
}
0