結果

問題 No.900 aδδitivee
ユーザー pekempey
提出日時 2019-10-04 22:19:16
言語 C++14
(gcc 9.2.0)
結果
AC  
実行時間 156 ms
コード長 3,329 Byte
コンパイル時間 1,884 ms
使用メモリ 19,184 KB
最終ジャッジ日時 2020-02-12 13:14:09

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
sample01 AC 0 ms
3,240 KB
sample02 AC 0 ms
3,328 KB
test_1_01 AC 4 ms
3,336 KB
test_1_02 AC 4 ms
3,336 KB
test_1_03 AC 4 ms
3,328 KB
test_1_04 AC 0 ms
3,272 KB
test_1_05 AC 0 ms
3,340 KB
test_2_01 AC 148 ms
13,004 KB
test_2_02 AC 144 ms
13,044 KB
test_2_03 AC 152 ms
12,976 KB
test_2_04 AC 156 ms
13,040 KB
test_2_05 AC 144 ms
12,956 KB
test_2_06 AC 152 ms
12,964 KB
test_2_07 AC 152 ms
13,040 KB
test_2_08 AC 148 ms
13,056 KB
test_2_09 AC 152 ms
13,068 KB
test_2_10 AC 140 ms
13,040 KB
test_2_11 AC 152 ms
12,980 KB
test_2_12 AC 148 ms
13,040 KB
test_2_13 AC 140 ms
12,956 KB
test_2_14 AC 148 ms
12,980 KB
test_2_15 AC 156 ms
13,004 KB
test_3_01 AC 128 ms
19,108 KB
test_3_02 AC 136 ms
19,104 KB
test_3_03 AC 140 ms
19,180 KB
test_3_04 AC 128 ms
19,140 KB
test_3_05 AC 136 ms
19,184 KB
test_3_06 AC 140 ms
19,100 KB
test_3_07 AC 140 ms
19,096 KB
テストケース一括ダウンロード

ソースコード

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