結果

問題 No.900 aδδitivee
コンテスト
ユーザー pekempey
提出日時 2019-10-04 22:19:16
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 128 ms / 2,000 ms
コード長 3,329 bytes
コンパイル時間 1,812 ms
コンパイル使用メモリ 178,272 KB
実行使用メモリ 20,532 KB
最終ジャッジ日時 2024-10-03 07:56:59
合計ジャッジ時間 6,194 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rep2(i, l, r) for (int i = (l); i < (r); i++)
#define rep2r(i, l, r) for (int i = (r) - 1; i >= (l); i--)
#define range(a) a.begin(), a.end()

using namespace std;
using ll = long long;

struct HLD {
  vector<int> label, parent, head;
  vector<int> L, R;

  HLD(const vector<vector<int>> &g) : label(g.size()), parent(g.size()), head(g.size()), L(g.size()), R(g.size()) {
    const int n = g.size();
    vector<int> size(n, 1);
    auto dfs = [&](auto dfs, int u, int p) -> void {
      for (int v : g[u]) if (v != p) {
        dfs(dfs, v, u);
        size[u] += size[v];
      }
    };
    dfs(dfs, 0, -1);
    int k = 0;
    auto dfs2 = [&](auto dfs, int u, int p, int h) -> void {
      L[u] = k;
      label[u] = k++;
      head[u] = h;
      parent[u] = p;
      for (int v : g[u]) if (v != p && size[v] * 2 >  size[u]) dfs(dfs, v, u, h);
      for (int v : g[u]) if (v != p && size[v] * 2 <= size[u]) dfs(dfs, v, u, v);
      R[u] = k;
    };
    dfs2(dfs2, 0, -1, 0);
  }

  int lca(int u, int v) {
    for (;;) {
      if (label[u] > label[v]) swap(u, v);
      if (head[u] == head[v]) return u;
      v = parent[head[v]];
    }
  }

  template<class F> void each(int u, int v, F f) {
    for (;;) {
      if (label[u] > label[v]) swap(u, v);
      if (head[u] == head[v]) {
        f(label[u], label[v]);
        return;
      }
      f(label[head[v]], label[v]);
      v = parent[head[v]];
    }
  }

  template<class F> void each_edge(int u, int v, F f) {
    for (;;) {
      if (label[u] > label[v]) swap(u, v);
      if (head[u] == head[v]) {
        if (u != v) f(label[u] + 1, label[v]);
        return;
      }
      f(label[head[v]], label[v]);
      v = parent[head[v]];
    }
  }

  int operator[](int u) {
    return label[u];
  };
};

struct bitrange {
  vector<long long> S0;
  vector<long long> S1;

  bitrange(int n) : S0(n + 1), S1(n + 1) {}

  void add0(int k, long long v) {
    for (int i = k + 1; i < S0.size(); i += i & -i) {
      S0[i] -= k * v;
      S1[i] += v;
    }
  }

  long long sum0(int k) {
    long long s0 = 0;
    long long s1 = 0;
    for (int i = k; i > 0; i -= i & -i) {
      s0 += S0[i];
      s1 += S1[i];
    }
    return s0 + s1 * k;
  }

  void add(int l, int r, long long v) {
    add0(l, v);
    add0(r, -v);
  }

  long long sum(int l, int r) {
    return sum0(r) - sum0(l);
  }
};



int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  int N; cin >> N;
  vector<vector<int>> G(N);
  vector<int> A(N - 1), B(N - 1), C(N - 1);
  rep(i, N - 1) {
    cin >> A[i] >> B[i] >> C[i];
    G[A[i]].emplace_back(B[i]);
    G[B[i]].emplace_back(A[i]);
  }
  HLD hld(G);
  bitrange bit(N);
  rep(i, N - 1) {
    if (hld[A[i]] < hld[B[i]]) {
      bit.add(hld[B[i]], hld[B[i]] + 1, C[i]);
    } else {
      bit.add(hld[A[i]], hld[A[i]] + 1, C[i]);
    }
  }
  int Q; cin >> Q;
  while (Q--) {
    int type; cin >> type;
    if (type == 1) {
      int a, x; cin >> a >> x;
      bit.add(hld.L[a] + 1, hld.R[a], x);
    } else {
      int a; cin >> a;
      ll ans = 0;
      hld.each_edge(a, 0, [&](int l, int r) {
        ans += bit.sum(l, r + 1);
      });
      cout << ans << '\n';
    }
  }
}
0