結果

問題 No.900 aδδitivee
コンテスト
ユーザー vjudge1
提出日時 2025-04-29 21:12:11
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 117 ms / 2,000 ms
コード長 2,633 bytes
コンパイル時間 2,386 ms
コンパイル使用メモリ 200,728 KB
実行使用メモリ 36,220 KB
最終ジャッジ日時 2025-04-29 21:12:18
合計ジャッジ時間 6,383 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int MAXN = 2e5 + 5, MAXL = 19;

int n, q, dep[MAXN], f[MAXN][MAXL], L[MAXN], R[MAXN], dfn_cnt;
ll dis[MAXN];
vector<pii> G[MAXN];

struct Edge{
  int u, v, w;
}e[MAXN];

void dfs(int u, int fa){
  L[u] = R[u] = ++dfn_cnt;
  dep[u] = dep[fa] + 1;
  for(const auto [v, w] : G[u]){
    dis[v] = dis[u] + w;
    dfs(v, u);
    R[u] = max(R[u], R[v]);
  }
}

struct Info{
  ll sum1, sum2;
  int len;
};

struct Tag{
  ll add1, add2;
  bool operator == (const Tag &i) const{
    return add1 == i.add1 && add2 == i.add2;
  }
};

struct SegTree{
  Info tr[MAXN << 2], E = {0, 0, 0};
  Tag tag[MAXN << 2], I = {0, 0};

  Info Comb(const Info &L, const Info &R){
    return {L.sum1 + R.sum1, L.sum2 + R.sum2, L.len + R.len};
  }

  Info F(const Info &x, const Tag &tg){
    return {x.sum1 + 1ll * x.len * tg.add1, x.sum2 + 1ll * x.len * tg.add2, x.len};
  }

  Tag f(const Tag &a, const Tag &b){
    return {a.add1 + b.add1, a.add2 + b.add2};
  }

  void Down(int i){
    if(tag[i] == I) return;
    tr[i << 1] = F(tr[i << 1], tag[i]);
    tag[i << 1] = f(tag[i << 1], tag[i]);
    tr[i << 1 | 1] = F(tr[i << 1 | 1], tag[i]);
    tag[i << 1 | 1] = f(tag[i << 1 | 1], tag[i]);
    tag[i] = I;
  }

  void Build(int i, int l, int r){
    tag[i] = I;
    if(l == r){
      tr[i] = {0, 0, 1};
      return;
    }
    int mid = (l + r) >> 1;
    Build(i << 1, l, mid); Build(i << 1 | 1, mid + 1, r);
    tr[i] = Comb(tr[i << 1], tr[i << 1 | 1]);
  }

  void Modify(int i, int l, int r, int ql, int qr, Tag tg){
    if(qr < l || r < ql) return;
    if(ql <= l && r <= qr){
      tr[i] = F(tr[i], tg);
      tag[i] = f(tag[i], tg);
      return;
    }
    Down(i);
    int mid = (l + r) >> 1;
    Modify(i << 1, l, mid, ql, qr, tg);
    Modify(i << 1 | 1, mid + 1, r, ql, qr, tg);
    tr[i] = Comb(tr[i << 1], tr[i << 1 | 1]);
  }

  Info Query(int i, int l, int r, int x){
    if(l == r) return tr[i];
    Down(i);
    int mid = (l + r) >> 1;
    return x <= mid ? Query(i << 1, l, mid, x) : Query(i << 1 | 1, mid + 1, r, x);
  }
}T;

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for(int i = 1, u, v, w; i < n; i++){
    cin >> u >> v >> w;
    u++, v++;
    G[u].push_back({v, w});
  }
  dfs(1, 0);
  T.Build(1, 1, n);
  cin >> q;
  for(int op, u, w; q; q--){
    cin >> op >> u;
    u++;
    if(op == 1){
      cin >> w;
      T.Modify(1, 1, n, L[u], R[u], {w, 1ll * w * dep[u]});
    }else{
      Info res = T.Query(1, 1, n, L[u]);
      cout << dis[u] + 1ll * res.sum1 * dep[u] - res.sum2 << "\n";
    }
  }
  return 0;
}
0