結果

問題 No.900 aδδitivee
ユーザー kusaf_kusaf_
提出日時 2024-10-03 13:31:55
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 147 ms / 2,000 ms
コード長 5,964 bytes
コンパイル時間 4,433 ms
コンパイル使用メモリ 281,564 KB
実行使用メモリ 28,404 KB
最終ジャッジ日時 2024-10-03 13:32:07
合計ジャッジ時間 8,905 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 1 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 116 ms
25,112 KB
testcase_08 AC 117 ms
25,108 KB
testcase_09 AC 122 ms
25,112 KB
testcase_10 AC 118 ms
25,108 KB
testcase_11 AC 117 ms
25,236 KB
testcase_12 AC 119 ms
25,108 KB
testcase_13 AC 117 ms
25,108 KB
testcase_14 AC 117 ms
25,116 KB
testcase_15 AC 147 ms
25,108 KB
testcase_16 AC 130 ms
24,980 KB
testcase_17 AC 119 ms
24,944 KB
testcase_18 AC 120 ms
25,108 KB
testcase_19 AC 130 ms
25,116 KB
testcase_20 AC 130 ms
25,108 KB
testcase_21 AC 127 ms
25,052 KB
testcase_22 AC 108 ms
28,272 KB
testcase_23 AC 111 ms
28,272 KB
testcase_24 AC 108 ms
28,276 KB
testcase_25 AC 108 ms
28,400 KB
testcase_26 AC 106 ms
28,404 KB
testcase_27 AC 104 ms
28,404 KB
testcase_28 AC 105 ms
28,272 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Tree : vector<vector<ll>> {
 private:
  void dfs_sz(int v, int p) {
    sz[v] = 1;
    ord.emplace_back(v);
    for(int i = p, x = 0; i != -1;) {
      bl[v][x] = i;
      i = bl[i][x], x++;
    }
    for(auto &nv : (*this)[v]) {
      if(nv == p) {
        if((int)(*this)[v].size() >= 2 && nv == (*this)[v][0]) { std::swap((*this)[v][0], (*this)[v][1]); }
        else { continue; }
      }
      dp[nv] = dp[v] + 1;
      dfs_sz(nv, v);
      sz[v] += sz[nv];
      if(sz[nv] > sz[(*this)[v][0]]) { std::swap(nv, (*this)[v][0]); }
    }
  }
  void dfs_hld(int v) {
    down[v] = id++;
    for(auto &nv : (*this)[v]) {
      if(nv == par(v)) { continue; }
      nx[nv] = (nv == (*this)[v][0] ? nx[v] : nv);
      dfs_hld(nv);
    }
    up[v] = id;
  }
  vector<pair<int, int>> ascend(int u, int v) const {
    vector<pair<int, int>> r;
    while(nx[u] != nx[v]) {
      r.emplace_back(down[u], down[nx[u]]);
      u = par(nx[u]);
    }
    if(u != v) { r.emplace_back(down[u], down[v] + 1); }
    return r;
  }
  vector<pair<int, int>> descend(int u, int v) const {
    if(u == v) { return {}; }
    if(nx[u] == nx[v]) { return {{down[u] + 1, down[v]}}; }
    auto r = descend(u, par(nx[v]));
    r.emplace_back(down[nx[v]], down[v]);
    return r;
  }

 public:
  int n, root, id = 0;
  vector<array<int, 24>> bl;
  vector<int> dp, sz, ord, down, up, nx;
  Tree(int n_, int r = 0): n(n_), root(r) { this->resize(n); }
  Tree(vector<vector<ll>> &g, int r = 0): n(g.size()), root(r) {
    *this = g;
    build();
  }
  void add_edge(int u, int v) {
    (*this)[u].emplace_back(v);
    (*this)[v].emplace_back(u);
  }
  void build() {
    bl.resize(n);
    dp.resize(n);
    sz.resize(n);
    down.assign(n, -1);
    up.assign(n, -1);
    nx.assign(n, root);
    for(auto &v : bl) { ranges::fill(v, -1); }
    dfs_sz(root, -1);
    dfs_hld(root);
  }
  int size() const { return n; }
  int depth(int i) const { return dp[i]; }
  int par(int i) const { return i == root ? root : bl[i][0]; }
  int order(int i) const { return ord[i]; }
  int in(int i) const { return down[i]; }
  int out(int i) const { return up[i]; }
  int size(int i) const { return sz[i]; }
  int kth_ancestor(int i, int k) const {
    if(dp[i] < k) { return -1; }
    while(k) {
      int t = __builtin_ctz(k);
      i = bl[i][t], k ^= 1 << t;
    }
    return i;
  }
  int dis(int u, int v) { return dp[u] + dp[v] - dp[lca(u, v)] * 2; }
  bool onpath(int u, int v, int x) { return dis(u, v) == dis(u, x) + dis(x, v); }
  int nxt(int u, int v) const {
    if(dp[u] >= dp[v]) { return par(u); }
    int x = kth_ancestor(v, dp[v] - dp[u] - 1);
    return bl[x][0] == u ? x : bl[u][0];
  }
  vector<int> path(int u, int v) const {
    vector<int> pre, suf;
    while(dp[u] > dp[v]) {
      pre.emplace_back(u);
      u = bl[u][0];
    }
    while(dp[u] < dp[v]) {
      suf.emplace_back(v);
      v = bl[v][0];
    }
    while(u != v) {
      pre.emplace_back(u);
      suf.emplace_back(v);
      u = bl[u][0];
      v = bl[v][0];
    }
    pre.emplace_back(u);
    ranges::reverse(suf);
    copy(suf.begin(), suf.end(), back_inserter(pre));
    return pre;
  }
  int lca(int u, int v) {
    while(nx[u] != nx[v]) {
      if(down[u] < down[v]) { std::swap(u, v); }
      u = par(nx[u]);
    }
    return dp[u] < dp[v] ? u : v;
  }
  int jump(int u, int v, int x) {
    int lc = lca(u, v), d1 = dp[u] - dp[lc];
    if(x <= d1) { return kth_ancestor(u, x); }
    int d = d1 + dp[v] - dp[lc];
    if(x <= d) { return kth_ancestor(v, d - x); }
    return -1;
  }
  vector<int> diameter() {
    int s = ranges::max_element(dp) - dp.begin();
    vector<int> d(n, -1);
    d[s] = 0;
    queue<int> q;
    q.emplace(s);
    while(!q.empty()) {
      int v = q.front();
      q.pop();
      for(auto &nv : (*this)[v]) {
        if(d[nv] == -1) {
          d[nv] = d[v] + 1;
          q.emplace(nv);
        }
      }
    }
    int t = ranges::max_element(d) - d.begin();
    return path(t, s);
  }
  template<typename F> void query(int u, int v, bool vertex, const F &f) {
    int l = lca(u, v);
    for(auto &&[a, b] : ascend(u, l)) {
      int s = a + 1, t = b;
      s > t ? f(t, s) : f(s, t);
    }
    if(vertex) f(down[l], down[l] + 1);
    for(auto &&[a, b] : descend(l, v)) {
      int s = a, t = b + 1;
      s > t ? f(t, s) : f(s, t);
    }
  }
  template<typename F> void noncommutative_query(int u, int v, bool vertex, const F &f) {
    int l = lca(u, v);
    for(auto &&[a, b] : ascend(u, l)) { f(a + 1, b); }
    if(vertex) { f(down[l], down[l] + 1); }
    for(auto &&[a, b] : descend(l, v)) { f(a, b + 1); }
  }
  template<typename F> void subtree_query(int u, bool vertex, const F &f) {
    f(down[u] + int(!vertex), up[u]);
  }
};

#include <atcoder/fenwicktree>
using namespace atcoder;

template<typename T> struct DualBIT {
  fenwick_tree<T> f1, f2;
  DualBIT(int N): f1(N + 1), f2(N + 1) {}
  void add(int i, T x) { add(i, i + 1, x); }
  void add(int l, int r, T x) {
    f1.add(l, x), f1.add(r, -x);
    f2.add(l, -x * (l - 1)), f2.add(r, x * (r - 1));
  }
  T sum(int i) { return f1.sum(0, i) * (i - 1) + f2.sum(0, i); }
  T sum(int l, int r) { return sum(r) - sum(l); }
  T operator[](int i) { return sum(i + 1) - sum(i); }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  ll N;
  cin >> N;

  Tree t(N);
  vector<tuple<ll, ll, ll>> e(N - 1);
  for(auto &[u, v, w] : e) {
    cin >> u >> v >> w;
    t.add_edge(u, v);
  }

  t.build();
  DualBIT<ll> B(N);
  for(auto &[u, v, w] : e) {
    if(t.depth(u) > t.depth(v)) { swap(u, v); }
    B.add(t.in(v), w);
  }

  ll Q;
  cin >> Q;
  while(Q--) {
    ll type, i, x;
    cin >> type >> i;
    if(type == 1) {
      cin >> x;
      t.subtree_query(i, false, [&](ll l, ll r) { B.add(l, r, x); });
    }
    else {
      ll ans = 0;
      t.query(0, i, false, [&](ll l, ll r) { ans += B.sum(l, r); });
      cout << ans << "\n";
    }
  }
}
0