結果

問題 No.900 aδδitivee
ユーザー CinnamorollCinnamoroll
提出日時 2019-10-05 18:36:11
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 239 ms / 2,000 ms
コード長 9,499 bytes
コンパイル時間 2,791 ms
コンパイル使用メモリ 178,600 KB
実行使用メモリ 33,016 KB
最終ジャッジ日時 2024-04-16 05:56:15
合計ジャッジ時間 9,608 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
7,100 KB
testcase_01 AC 5 ms
7,168 KB
testcase_02 AC 6 ms
7,296 KB
testcase_03 AC 7 ms
7,168 KB
testcase_04 AC 6 ms
7,168 KB
testcase_05 AC 5 ms
7,168 KB
testcase_06 AC 5 ms
7,168 KB
testcase_07 AC 231 ms
27,828 KB
testcase_08 AC 232 ms
27,844 KB
testcase_09 AC 239 ms
27,792 KB
testcase_10 AC 236 ms
27,784 KB
testcase_11 AC 227 ms
27,820 KB
testcase_12 AC 231 ms
27,960 KB
testcase_13 AC 233 ms
27,780 KB
testcase_14 AC 232 ms
27,860 KB
testcase_15 AC 234 ms
28,164 KB
testcase_16 AC 231 ms
28,140 KB
testcase_17 AC 236 ms
27,840 KB
testcase_18 AC 229 ms
27,784 KB
testcase_19 AC 231 ms
27,864 KB
testcase_20 AC 231 ms
27,880 KB
testcase_21 AC 225 ms
27,856 KB
testcase_22 AC 213 ms
32,612 KB
testcase_23 AC 220 ms
32,580 KB
testcase_24 AC 225 ms
32,680 KB
testcase_25 AC 219 ms
32,684 KB
testcase_26 AC 220 ms
32,588 KB
testcase_27 AC 221 ms
32,656 KB
testcase_28 AC 221 ms
33,016 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// warm heart, wagging tail,and a smile just for you!
//                                                                     ███████████
//                                                                   ███╬╬╬╬╬╬╬╬╬╬███
//                                                                ███╬╬╬╬╬████╬╬╬╬╬╬███
//                                            ███████████       ██╬╬╬╬╬████╬╬████╬╬╬╬╬██
//                                      █████████╬╬╬╬╬████████████╬╬╬╬╬██╬╬╬╬╬╬███╬╬╬╬╬██
//                               ████████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████████╬╬╬╬╬╬██╬╬╬╬╬╬╬██
//                             ████╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████████╬╬╬╬╬╬╬╬╬╬╬██
//                           ███╬╬╬█╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬███╬╬╬╬╬╬╬█████
//                         ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬████████╬╬╬╬╬██
//                       ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬╬╬╬╬╬███
//                     ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬██
//                 ████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████╬╬╬╬╬████
//     █████████████╬╬╬╬╬╬╬╬██╬╬╬╬╬████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬██████
//   ████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬██████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██████╬╬╬╬╬╬╬███████████╬╬╬╬╬╬╬╬██╬╬╬██╬╬╬██
// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████╬╬╬╬╬╬╬╬╬╬╬█╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬██
// ██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬▓▓▓▓▓▓╬╬╬████╬╬████╬╬╬╬╬╬╬▓▓▓▓▓▓▓▓██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬███
// ██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██████▓▓▓▓▓▓▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓▓▓▓▓▓▓██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬█████
// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████████
//   ███╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██
//       ██████████████  ████╬╬╬╬╬╬███████████████████████████╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████
//                         ███████                           █████  ███████████████████  
//
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
const double EPS = 1e-9;
#define INF (1LL<<60)
#define D double
#define fs first
#define sc second
#define int long long
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for(int i = (b-1);i>=(a);--i)
#define REP(i,n)  FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SP << " " << 
typedef pair<int,int> P;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

template <typename T,typename E>
struct SegmentTree{
  using F = function<T(T,T)>;
  using G = function<T(T,E,int)>;
  using H = function<E(E,E)>;
  int n;
  F f;
  G g;
  H h;
  T ti;
  E ei;
  vector<T> dat;
  vector<E> laz;
  SegmentTree(F f,G g,H h,T ti,E ei):
    f(f),g(g),h(h),ti(ti),ei(ei){}

  void init(int n_){
    n=1;
    while(n<n_) n<<=1;
    dat.assign((n<<1)-1,ti);
    laz.assign((n<<1)-1,ei);
  }
  void build(const vector<T> &v){
    int n_=v.size();
    init(n_);
    for(int i=0;i<n_;i++) dat[n+i-1]=v[i];
    for(int i=n-2;i>=0;i--)
      dat[i]=f(dat[(i<<1)+2],dat[(i<<1)|1]);
  }
  void eval(int k,int l,int r){
    if(laz[k]==ei)return;
    dat[k] = g(dat[k], laz[k], r-l);
    if(r-l>1){
      laz[(k<<1)|1] = h(laz[(k<<1)|1], laz[k]);
      laz[(k<<1)+2] = h(laz[(k<<1)+2], laz[k]);
    }
    laz[k]=ei;
  }

  void update(int a, int b, E x,int k=0,int l=0,int r=-1){
    if(r<0)r=n;
    eval(k,l,r);
    if(r<=a||b<=l)return;
    if(a<=l&&r<=b){
      laz[k] = h(laz[k], x);
      eval(k,l,r);
    }
    else {
      update(a,b,x,(k<<1)|1,l,(l+r)/2);
      update(a,b,x,(k<<1)+2,(l+r)/2,r);
      dat[k]=f(dat[(k<<1)|1], dat[(k<<1)+2]);
    }
  }

  T query(int a,int b,int k=0,int l=0,int r=-1){
    if(r<0)r=n;
    eval(k,l,r);
    if(r<=a||b<=l)return ti;
    if(a<=l&&r<=b)return dat[k];
    T xl=query(a,b,(k<<1)|1,l,(l+r)/2);
    T xr=query(a,b,(k<<1)+2,(l+r)/2,r);
    return f(xl, xr);
  }

  //lower_find(l,r,fanc): fancを満たす区間[0,id)なるidの最小値を返す. ng < okのとき
  template<typename C>
  int lower_find(int a, int b, C &check, T x, int k=1, int l=0, int r=-1){
    if(r<0)r=n;
    if(!check(f(x,dat[k]))||r<=a||b<=l)return -1;
    if(r-l==1)return l;
    int xl = lower_find(a,b,check,x,(k<<1),l,(l+r)/2);
    if(xl>=0)return xl;
    x = f(x,dat[(k<<1)]);
    return lower_find(a,b,check,x,(k<<1)|1,(l+r)/2,r);
  }
  template<typename C>
  int lower_find(int a, int b, C &check){
    T x=ti;
    return lower_find(a,b,check,x);
  }

  //upper_find(l,r,fanc): fancを満たす区間[0,id)なるidの最小値を返す. ok < ngのとき
  template<typename C>
  int upper_find(int a, int b, C &check, T x, int k=2, int l=0, int r=-1){
    if(r<0)r=n;
    if(r<=a||b<=l)return -1;
    if(r-l==1)return l;
    if(check(f(x,dat[k]))){
      int xr = upper_find(a,b,check,f(x,dat[k]),((k+1)<<1),(l+r)/2,r);
      if(xr>=0)return xr;
    }
    return upper_find(a,b,check,x,(k<<1),l,(l+r)/2);
  }
  template<typename C>
  int upper_find(int a, int b, C &check){
    T x=ti;
    return upper_find(a,b,check,x);
  }
};

//ex) RAQ & RSQ
//auto f = [](int a, int b){return a+b;};
//auto g = [](int a, int b, int len){return a+b*len;};
//auto h = [](int a, int b){return a+b;};

//ex) RAQ & RMQ
//auto f = [](int a, int b){return min(a,b);};
//auto g = [](int a, int b, int len){return a+b;};
//auto h = [](int a, int b){return a+b;};

const int N = 1e5+10;
vector<P> edge[N],path;
vector<int> l(N),r(N);

void dfs(int no, int par){
  l[no] = path.size();
  for(P to: edge[no]){
    if(to.fs==par) continue;
    path.emplace_back(to.sc,1);
    dfs(to.fs,no);
    path.emplace_back(-to.sc,-1);
  }
  r[no] = path.size();
}

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n;
  cin >> n;

  REP(_,n-1){
    int x,y,c;
    cin >> x >> y >> c;
    edge[x].emplace_back(y,c);
    edge[y].emplace_back(x,c);
  }

  dfs(0,-1);
  //REP(i,n) cout << l[i] SP r[i] << endl;

  auto f = [](P a, P b){return P(a.fs+b.fs,a.sc+b.sc);};
  auto g = [](P a, int b, int len){return P(a.fs+b*a.sc,a.sc);};
  auto h = [](int a, int b){return a+b;};
  SegmentTree<P,int> seg(f,g,h,P(0,0),0);
  seg.build(path);

  //REP(i,path.size()) cout << path[i].fs SP path[i].sc << endl;

  int q; cin >> q;
  REP(_,q){
    int k; cin >> k;
    if(k==1){
      int a,x; cin >> a >> x;
      seg.update(l[a],r[a],x);
    }
    else{
      int b; cin >> b;
      cout << seg.query(0,l[b]).fs << "\n";
    }
  }

  return 0;
}
0