結果

問題 No.900 aδδitivee
ユーザー vjudge1
提出日時 2025-04-29 21:12:34
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 135 ms / 2,000 ms
コード長 1,867 bytes
コンパイル時間 2,369 ms
コンパイル使用メモリ 197,760 KB
実行使用メモリ 18,816 KB
最終ジャッジ日時 2025-04-29 21:12:41
合計ジャッジ時間 7,042 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 1e5 + 1, MAXL = 17;

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

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

int n, q, dep[MAXN];
int dfn_l[MAXN], dfn_r[MAXN], tot;
vector<pair<int, int>> g[MAXN];

struct SegTree {
  Tag tag[MAXN << 2], I = {0, 0};
  Tag F(const Tag &tag1, const Tag &tag2) {
    return {tag1.k + tag2.k, tag1.b + tag2.b};
  }
  void modify(int o, int l, int r, int ql, int qr, Tag &t) {
    if (ql <= l && r <= qr) {
      tag[o] = F(t, tag[o]);
      return;
    }
    if (ql > r || qr < l) {
      return;
    }
    int mid = (l + r) >> 1;
    modify(o << 1, l, mid, ql, qr, t), modify(o << 1 | 1, mid + 1, r, ql, qr, t);
  }
  Tag query(int o, int l, int r, int i, Tag t) {
    t = F(t, tag[o]);
    if (l == r) {
      return t;
    }
    int mid = (l + r) >> 1;
    return i <= mid ? query(o << 1, l, mid, i, t) : query(o << 1 | 1, mid + 1, r, i, t);
  }
} T;

void dfs(int u) {
  dfn_l[u] = dfn_r[u] = ++tot;
  for (auto [v, w] : g[u]) {
    dep[v] = dep[u] + 1;
    dfs(v);
    dfn_r[u] = max(dfn_r[u], dfn_r[v]);
  }
}

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++;
    e[i] = {u, v, w};
    g[u].push_back({v, w});
  }
  dfs(1);
  for (int i = 1; i < n; i++) {
    Tag t = {0, e[i].w};
    T.modify(1, 1, n, dfn_l[e[i].v], dfn_r[e[i].v], t);
  }
  cin >> q;
  for (int i = 1, op, u, x; i <= q; i++) {
    cin >> op >> u, u++;
    if (op == 1) {
      cin >> x;
      Tag t = {x, -1ll * dep[u] * x};
      T.modify(1, 1, n, dfn_l[u], dfn_r[u], t);
    } else {
      auto t = T.query(1, 1, n, dfn_l[u], {0, 0});
      ll ans = 1ll * dep[u] * t.k + t.b;
      cout << ans << '\n';
    }
  }
  return 0;
}
0