結果

問題 No.900 aδδitivee
ユーザー onakasuitacityonakasuitacity
提出日時 2019-10-13 08:42:42
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 189 ms / 2,000 ms
コード長 4,088 bytes
コンパイル時間 3,752 ms
コンパイル使用メモリ 196,132 KB
実行使用メモリ 32,752 KB
最終ジャッジ日時 2024-05-08 06:27:38
合計ジャッジ時間 9,952 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 3 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 183 ms
29,784 KB
testcase_08 AC 185 ms
29,992 KB
testcase_09 AC 182 ms
29,796 KB
testcase_10 AC 180 ms
29,812 KB
testcase_11 AC 182 ms
29,800 KB
testcase_12 AC 183 ms
29,780 KB
testcase_13 AC 182 ms
29,808 KB
testcase_14 AC 189 ms
29,760 KB
testcase_15 AC 183 ms
29,784 KB
testcase_16 AC 187 ms
29,776 KB
testcase_17 AC 178 ms
29,840 KB
testcase_18 AC 181 ms
29,808 KB
testcase_19 AC 184 ms
29,784 KB
testcase_20 AC 181 ms
29,808 KB
testcase_21 AC 180 ms
29,872 KB
testcase_22 AC 172 ms
32,672 KB
testcase_23 AC 174 ms
32,696 KB
testcase_24 AC 171 ms
32,584 KB
testcase_25 AC 172 ms
32,700 KB
testcase_26 AC 174 ms
32,720 KB
testcase_27 AC 175 ms
32,752 KB
testcase_28 AC 186 ms
32,672 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std; void solve(); int main(){cin.tie(0); ios::sync_with_stdio(false); cout<<fixed<<setprecision(10); solve();}
using ll=int_fast64_t; using ld=long double; using pll=pair<ll,ll>; using pld=pair<ld,ld>;
#define fi first
#define se second
#define SELECTOR(_1,_2,_3,SELECT,...) SELECT
#define rep(...) SELECTOR(__VA_ARGS__,_rep1,_rep0)(__VA_ARGS__)
#define _rep0(i,n) for(ll i=0;i<n;++i)
#define _rep1(i,k,n) for(ll i=k;i<n;++i)
template<class T> void vecout(const T &v){for(auto it=v.begin();it!=v.end();++it,cout<<(it!=v.end()?" ":"\n"))cout<<*it;}

template<class T,class E>
class SegmentTree{
  using F=function<T(T,T)>;
  using G=function<E(E,E)>;
  using H=function<T(E,T)>;
private:
  ll n=1;
  F dot;
  T e;
  G comp;
  E id;
  H act;
  vector<T> node;
  vector<E> lazy;
  constexpr inline void propagate(ll i){
    if(lazy[i]==id) return;
    if(i<=n-1){
      lazy[2*i]=comp(lazy[2*i],lazy[i]);
      lazy[2*i+1]=comp(lazy[2*i+1],lazy[i]);
    }
    node[i]=act(lazy[i],node[i]);
    lazy[i]=id;
  }
  void ancestors_propagate(ll i){
    if(i==1) return;
    ancestors_propagate(i>>=1);
    propagate(i);
  }
  constexpr inline void update_ancestors(ll i){
    while(i!=1){
      propagate(i+1-2*(i%2));
      i>>=1;
      node[i]=dot(node[2*i],node[2*i+1]);
    }
  }
public:
  constexpr SegmentTree(const vector<T> &A,F dot,T e,G comp,E id,H act)
  :dot(dot),e(e),comp(comp),id(id),act(act){
    while(n<A.size()) n<<=1;
    node.resize(2*n,e);
    lazy.resize(2*n,id);
    rep(i,A.size()) node[n+i]=A[i];
    for(ll i=n-1;i>0;--i) node[i]=dot(node[2*i],node[2*i+1]);
  }
  constexpr void update(ll i,T c){
    ancestors_propagate(i+=n);
    propagate(i);
    node[i]=c;
    update_ancestors(i);
  }
  constexpr void add(ll l,ll r,E f){
    vector<ll> range,low(2);
    for(l+=n,r+=n;l<r;l>>=1,r>>=1){
      if(l%2==1){
        if(!low[0]) low[0]=l;
        range.push_back(l++);
      }
      if(r%2==1){
        range.push_back(--r);
        if(!low[1]) low[1]=r;
      }
    }
    for(ll i:low) if(i) ancestors_propagate(i);
    for(ll i:range) lazy[i]=comp(lazy[i],f);
    for(ll i:low) if(i){
      propagate(i);
      update_ancestors(i);
    }
  }
  constexpr T sum(ll l,ll r){
    T vl=e, vr=e;
    pair<bool,bool> low;
    for(l+=n,r+=n;l<r;l>>=1,r>>=1){
      if(l%2==1){
        if(!low.first){
          ancestors_propagate(l);
          low.first=true;
        }
        propagate(l);
        vl=dot(vl,node[l]);
        l++;
      }
      if(r%2==1){
        r--;
        if(!low.second){
          ancestors_propagate(r);
          low.second=true;
        }
        propagate(r);
        vr=dot(node[r],vr);
      }
    }
    return dot(vl,vr);
  }
};

class EulerTour{
private:
  ll m_n;
  vector<vector<pll>> E;
  vector<ll> m_begin,m_end;
  vector<pll> m_tour;
  ll i=0;
  void dfs(ll v,ll p){
    m_begin[v]=i++;
    for(const pll& u:E[v]){
      if(u.fi==p) continue;
      m_tour[i]=make_pair(u.se,1);
      dfs(u.fi,v);
      m_tour[i++]=make_pair(-u.se,-1);
    }
    m_end[v]=i;
  }
public:
  EulerTour(const vector<vector<pll>>& E,ll root=0):E(E){
    m_n=E.size();
    m_begin.resize(m_n);
    m_end.resize(m_n);
    m_tour.resize(2*m_n-1);
    m_tour[0]=make_pair(0,0);
    dfs(root,-1);
  }
  const vector<ll>& begin(){return m_begin;}
  const vector<ll>& end(){return m_end;}
  const vector<pll>& tour(){return m_tour;}
};

void solve(){
  ll n; cin>>n;
  vector<vector<pll>> E(n);
  rep(_,n-1){
    ll u,v,w; cin>>u>>v>>w;
    E[u].emplace_back(v,w);
  }
  // build
  auto tour=EulerTour{E};
  auto dot=[](pll a,pll b){return make_pair(a.fi+b.fi,a.se+b.se);};
  pll e=make_pair(0,0);
  auto comp=[](ll f,ll g){return g+f;};
  ll id=0;
  auto act=[](ll f,pll a){return make_pair(a.fi+f*a.se,a.se);};
  auto tree=SegmentTree<pll,ll>(tour.tour(),dot,e,comp,id,act);
  // query
  ll q; cin>>q;
  rep(_,q){
    ll c; cin>>c;
    if(c==1){
      ll a,x; cin>>a>>x;
      tree.add(tour.begin()[a]+1,tour.end()[a],x);
    } else {
      ll b; cin>>b;
      cout<<tree.sum(0,tour.begin()[b]+1).fi<<"\n";
    }
  }
}
0