結果

問題 No.900 aδδitivee
ユーザー saxofone111saxofone111
提出日時 2021-03-10 19:00:25
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 346 ms / 2,000 ms
コード長 6,025 bytes
コンパイル時間 2,618 ms
コンパイル使用メモリ 212,148 KB
実行使用メモリ 25,916 KB
最終ジャッジ日時 2024-04-20 13:55:40
合計ジャッジ時間 12,312 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 3 ms
5,376 KB
testcase_02 AC 3 ms
5,376 KB
testcase_03 AC 3 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 341 ms
20,908 KB
testcase_08 AC 335 ms
20,872 KB
testcase_09 AC 335 ms
20,912 KB
testcase_10 AC 339 ms
21,032 KB
testcase_11 AC 344 ms
20,912 KB
testcase_12 AC 340 ms
21,028 KB
testcase_13 AC 346 ms
20,872 KB
testcase_14 AC 334 ms
21,036 KB
testcase_15 AC 332 ms
20,908 KB
testcase_16 AC 342 ms
20,828 KB
testcase_17 AC 343 ms
20,900 KB
testcase_18 AC 326 ms
20,820 KB
testcase_19 AC 342 ms
20,972 KB
testcase_20 AC 342 ms
20,824 KB
testcase_21 AC 342 ms
20,832 KB
testcase_22 AC 324 ms
25,784 KB
testcase_23 AC 322 ms
25,788 KB
testcase_24 AC 311 ms
25,632 KB
testcase_25 AC 321 ms
25,788 KB
testcase_26 AC 310 ms
25,756 KB
testcase_27 AC 316 ms
25,916 KB
testcase_28 AC 322 ms
25,728 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define rrep(i, n) for(ll i=(n)-1; i >=0; i--)
#define ALL(v) v.begin(),v.end()
#define rALL(v) v.rbegin(),v.rend()
#define FOR(i, j, k) for(ll i=j;i<k;i++)
#define debug_print(var) cerr << #var << "=" << var <<endl;
#define DUMP(i, v)for(ll i=0;i<v.size();i++)cerr<<v[i]<<" "
#define fi first
#define se second

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<ll, ll> P;
typedef long double ld;
struct edge{ll x, c;};

ll N;

template <class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
struct lazy_segtree {
public:
  int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
  }
  lazy_segtree() : lazy_segtree(0) {}
  lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
  lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
    log = ceil_pow2(_n);
    size = 1 << log;
    d = std::vector<S>(2 * size, e());
    lz = std::vector<F>(size, id());
    for (int i = 0; i < _n; i++) d[size + i] = v[i];
    for (int i = size - 1; i >= 1; i--) {
      update(i);
    }
  }

  void set(int p, S x) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    d[p] = x;
    for (int i = 1; i <= log; i++) update(p >> i);
  }

  S get(int p) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    return d[p];
  }

  S prod(int l, int r) {
    assert(0 <= l && l <= r && r <= _n);
    if (l == r) return e();

    l += size;
    r += size;

    for (int i = log; i >= 1; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push(r >> i);
    }

    S sml = e(), smr = e();
    while (l < r) {
      if (l & 1) sml = op(sml, d[l++]);
      if (r & 1) smr = op(d[--r], smr);
      l >>= 1;
      r >>= 1;
    }

    return op(sml, smr);
  }

  S all_prod() { return d[1]; }

  void apply(int p, F f) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    d[p] = mapping(f, d[p]);
    for (int i = 1; i <= log; i++) update(p >> i);
  }

  void apply(int l, int r, F f) {
    assert(0 <= l && l <= r && r <= _n);
    if (l == r) return;

    l += size;
    r += size;

    for (int i = log; i >= 1; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push((r - 1) >> i);
    }

    {
      int l2 = l, r2 = r;
      while (l < r) {
        if (l & 1) all_apply(l++, f);
        if (r & 1) all_apply(--r, f);
        l >>= 1;
        r >>= 1;
      }
      l = l2;
      r = r2;
    }

    for (int i = 1; i <= log; i++) {
      if (((l >> i) << i) != l) update(l >> i);
      if (((r >> i) << i) != r) update((r - 1) >> i);
    }
  }

  template <bool (*g)(S)> int max_right(int l) {
    return max_right(l, [](S x) { return g(x); });
  }
  template <class G> int max_right(int l, G g) {
    assert(0 <= l && l <= _n);
    assert(g(e()));
    if (l == _n) return _n;
    l += size;
    for (int i = log; i >= 1; i--) push(l >> i);
    S sm = e();
    do {
      while (l % 2 == 0) l >>= 1;
      if (!g(op(sm, d[l]))) {
        while (l < size) {
          push(l);
          l = (2 * l);
          if (g(op(sm, d[l]))) {
            sm = op(sm, d[l]);
            l++;
          }
        }
        return l - size;
      }
      sm = op(sm, d[l]);
      l++;
    } while ((l & -l) != l);
    return _n;
  }

  template <bool (*g)(S)> int min_left(int r) {
    return min_left(r, [](S x) { return g(x); });
  }
  template <class G> int min_left(int r, G g) {
    assert(0 <= r && r <= _n);
    assert(g(e()));
    if (r == 0) return 0;
    r += size;
    for (int i = log; i >= 1; i--) push((r - 1) >> i);
    S sm = e();
    do {
      r--;
      while (r > 1 && (r % 2)) r >>= 1;
      if (!g(op(d[r], sm))) {
        while (r < size) {
          push(r);
          r = (2 * r + 1);
          if (g(op(d[r], sm))) {
            sm = op(d[r], sm);
            r--;
          }
        }
        return r + 1 - size;
      }
      sm = op(d[r], sm);
    } while ((r & -r) != r);
    return 0;
  }

private:
  int _n, size, log;
  std::vector<S> d;
  std::vector<F> lz;

  void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
  void all_apply(int k, F f) {
    d[k] = mapping(f, d[k]);
    if (k < size) lz[k] = composition(f, lz[k]);
  }
  void push(int k) {
    all_apply(2 * k, lz[k]);
    all_apply(2 * k + 1, lz[k]);
    lz[k] = id();
  }
};

struct S{
  ll x, d;
};

struct F{
  ll a, b;
};

S op(S a, S b){
    return {a.x+b.x, a.d+b.d};
}

S mapping(F a, S b){
  return {b.x + a.a*b.d + a.b, b.d};
}

F composition(F b, F a){
  return {b.a + a.a, a.b + b.b};
}

S e(){
  return {0, 0};
}

F id(){
  return {0, 0};
}

//usage lazy_segtree<S, op, e, F, mapping, composition, id>
vector<S> a;
vector<vector<edge>> ed;
vector<P> range;
llvec d;

void dfs(ll from, ll to, ll c){
  range[to].fi = a.size();
  a.push_back({c, d[to]});
  for(auto ie: ed[to]){
    if(ie.x==from)continue;
    d[ie.x] = d[to] + 1;
    dfs(to, ie.x, c+ie.c);
  }
  range[to].se = a.size();
}
/**************************************
** A main function starts from here  **
***************************************/
int main(){
  ll N;
  cin >> N;
  ed = vector<vector<edge>>(N);
  range = vector<P>(N);
  rep(i, N-1){
    ll a, b, c;
    cin >> a >> b >> c;
    ed[a].push_back({b, c});
    ed[b].push_back({a, c});
  }
  d = llvec(N, 0);
  dfs(-1, 0, 0);
  lazy_segtree<S, op, e, F, mapping, composition, id> lz(a);
  ll Q;
  cin >> Q;
  while(Q--){
    ll t;
    cin >> t;
    if(t==1){
      ll a, x;
      cin >> a >> x;
      lz.apply(range[a].fi, range[a].se, {x, -d[a]*x});
    }else{
      ll b;
      cin >> b;
      auto ans = lz.prod(range[b].fi, range[b].fi+1);
      cout << ans.x <<endl;
    }
  }
  
  return 0;
}
0