結果

問題 No.900 aδδitivee
ユーザー Jiro_tech15Jiro_tech15
提出日時 2019-10-04 23:19:59
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 6,872 bytes
コンパイル時間 1,728 ms
コンパイル使用メモリ 96,360 KB
実行使用メモリ 118,404 KB
最終ジャッジ日時 2024-10-03 08:54:39
合計ジャッジ時間 11,332 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <stack>
#include <set>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()

ll mpow(ll a, ll b){
  if(b==0) return 1;
  else if(b%2==0){ll memo = mpow(a,b/2); return memo*memo%MOD;}
  else return mpow(a,b-1) * a % MOD;
}
ll lpow(ll a, ll b){
  if(b==0) return 1;
  else if(b%2==0){ll memo = lpow(a,b/2); return memo*memo;}
  else return lpow(a,b-1) * a;
}
ll gcd(ll a, ll b){
  if(b==0) return a;
  else return gcd(b, a%b);
}
vector<ll> kaijo_memo;
ll kaijo(ll n){
  if(kaijo_memo.size() > n) return kaijo_memo[n];
  if(kaijo_memo.size() == 0) kaijo_memo.push_back(1);
  while(kaijo_memo.size() <= n) kaijo_memo.push_back(kaijo_memo[kaijo_memo.size()-1] * kaijo_memo.size() % MOD);
  return kaijo_memo[n];
}
vector<ll> gyaku_kaijo_memo;
ll gyaku_kaijo(ll n){
  if(gyaku_kaijo_memo.size() > n) return gyaku_kaijo_memo[n];
  if(gyaku_kaijo_memo.size() == 0) gyaku_kaijo_memo.push_back(1);
  while(gyaku_kaijo_memo.size() <= n) gyaku_kaijo_memo.push_back(gyaku_kaijo_memo[gyaku_kaijo_memo.size()-1] * mpow(gyaku_kaijo_memo.size(), MOD-2) % MOD);
  return gyaku_kaijo_memo[n];
}

ll nCr(ll n, ll r){
  if(n == r) return 1;//0個の丸と-1個の棒みたいな時に時に効く？不安.
  if(n < r || r < 0) return 0;
  ll ret = 1;
  ret *= kaijo(n); ret %= MOD;
  ret *= gyaku_kaijo(r); ret %= MOD;
  ret *= gyaku_kaijo(n-r); ret %= MOD;
  return ret;
}

const int MAX_N = 1 << 20;

//葉の数
int N;
//扱うデータ型をllとしている.適宜修正.
ll dat[2 * MAX_N - 1];
//vectorにするのもあり
ll lazy[2 * MAX_N - 1];

void init(int n_){
  //簡単のため, 要素数を2のべき乗に
  N = 1;
  while(N < n_) N *= 2;

  //初期化処理をここに書く
  rep(i,2 * N - 1){
    dat[i] = 0;
    lazy[i] = 0;
  }
}

//[a,b)にxを加算
void update(int a, int b, ll x, int now, int l, int r){
  //[a,b)と[l,r)が交差しなければ, 無を返す.
  //評価値が最小値ならばINT_MAX. 修正すること.
  if(r <= a || b <= l) return;
  // [a, b)が[l, r)を完全に含んでいれば
  if(a <= l && r <= b){
    lazy[now] += (x * (b-a));
  }else{
    //そうでなければ, 2つの個の複合値
    //ここでは, 2つの子の最小値. 修正すること.
    dat[now] += (x * (min(b,r) - max(a,l)));
    update(a, b, x, now*2+1, l, (l+r)/2);
    update(a, b, x, now*2+2, (l+r)/2, r);
  }
/*
  //葉のノード番号
  k += N-1;

  //葉の更新処理をここに書く.
  dat[k] = a;

  //登りながら更新.
  while(k > 0){
    k = (k-1) / 2;
    //中間ノードの更新処理をここに書く.
    dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
  }
*/
}

//[a,b)における評価値を得る. ここでは最小値としている.
//nowが現在の接点番号, nowは[l, r)に対応している.
//呼ぶ時は query(a,b,0,0,N)
ll query(int a, int b, int now, int l, int r){
  //[a,b)と[l,r)が交差しなければ, 無を返す.
  //評価値が最小値ならばINT_MAX. 修正すること.
  if(r <= a || b <= l) return 0;

  // [a, b)が[l, r)を完全に含んでいれば, このノードの値
  if(a <= l && r <= b){
    ll ret = dat[now];
    ret += lazy[now];
    return ret;
  }else{
    //そうでなければ, 2つの個の複合値
    //ここでは, 2つの子の最小値. 修正すること.
    lazy[now*2+1] += lazy[now]/2;
    lazy[now*2+2] += lazy[now]/2;
    lazy[now] = 0;
    ll vl = query(a, b, now*2+1, l, (l+r)/2);
    ll vr = query(a, b, now*2+2, (l+r)/2, r);
    return vl + vr;
  }
}


struct edge{ll cost; int to;};
vector<edge> G[MAX_N];
vector<int> P[MAX_N];
bool checked[MAX_N];
int number[MAX_N],first[MAX_N],first_m[MAX_N],last[MAX_N],last_m[MAX_N],D[MAX_N];
vector<ll> tour, tour_m;

int dfs(int now, int num, int depth){
  D[now] = depth;
  checked[now] = true;
  number[now] = num;
  num++;
  first[now] = tour.size();
  first_m[now] = tour_m.size();
  rep(i,G[now].size()){
    int next = G[now][i].to;
    if(checked[next]) continue;
    tour.push_back(G[now][i].cost);
    P[next].push_back(now);
    int ret = dfs(next, num, depth+1);
    if(ret == -1) continue;
    num = ret;
    tour_m.push_back(G[now][i].cost);
  }
  last[now] = tour.size() - 1;
  last_m[now] = tour_m.size() - 1;
  return num;
}

int lca(int a, int b){
  REP(t,30){
    if(D[a] - lpow(2,t) >= D[b]){
      a = P[a][t];
    }else if(D[b] - lpow(2,t) >= D[a]){
      b = P[b][t];
    }
  }

  REP(t,30){
    if(P[a][t] != P[b][t]){
      a = P[a][t];
      b = P[b][t];
    }
  }
  if(a != b){
    a = P[a][0];
    b = P[b][0];
  }
  if(a != b){
    cout<<"おかしいよ！"<<endl;
    while(true){

    }
  }
  return a;
}

int main(void){
  int n;cin>>n;
  rep(i,n-1){
    int u,v,w;
    cin>>u>>v>>w;
    G[u].push_back({w,v});
    G[v].push_back({w,u});
  }

  rep(i,n){
    checked[i] = false;
  }

  P[0].push_back(-1);
  dfs(0, 0, 0);
  rep(t,30){
    rep(i,n){
      if(P[i][t] == -1){
        P[i].push_back(-1);
        continue;
      }
      P[i].push_back(P[P[i][t]][t]);
    }
  }

  /*rep(i,n){
    cout<<number[i]<<" ";
  }
  cout<<endl;

  rep(i,tour.size()){
    cout<<tour[i]<<" ";
  }
  cout<<endl;

  rep(i,n){
    cout<<P[i][1]<<" ";
  }
  cout<<endl;*/

  ll skip = tour.size();
  rep(i,tour.size()){
    update(i,i+1,tour[i],0,0,MAX_N);
  }
  rep(i,tour_m.size()){
    update(i+skip,i+1+skip,tour_m[i],0,0,MAX_N);
  }

  int q;cin>>q;

  rep(i,q){
    int kind;cin>>kind;
    if(kind == 1){
      ll a,x;
      cin>>a>>x;
      update(first[a], last[a]+1, x, 0, 0, MAX_N);
      update(first_m[a]+skip, last_m[a]+1+skip, x, 0, 0, MAX_N);
    }else{
      ll b;
      cin>>b;
      cout<<query(0,first[b],0,0,MAX_N) - query(0+skip,first_m[b]+skip,0,0,MAX_N)<<endl;
    }
  }
  update(0,MAX_N,2,0,0,MAX_N);
  /*rep(i,q){
    int k = 3;
    vector<pair<ll,ll>> X;
    rep(j,k){
      ll x;cin>>x;
      X.push_back({number[x], x});
    }
    sort(all(X));
    ll ans = 0;
    rep(j,X.size()){
      ll a = X[j].second;
      ll b = X[(j+1)%X.size()].second;
      ll p = lca(a,b);
      //cout<<a<<" "<<b<<" "<<p<<" "<<tour[first[b]-1] - tour[first[p]-1] + tour[first[a]-1] - tour[first[p]-1]<<endl;
      ans += tour[first[b]-1] - tour[first[p]-1] + tour[first[a]-1] - tour[first[p]-1];
    }
    cout<<ans/2<<endl;
  }*/

  return 0;
}
0