結果

問題 No.900 aδδitivee
ユーザー 👑 hos.lyrichos.lyric
提出日時 2019-10-04 21:53:25
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 255 ms / 2,000 ms
コード長 4,348 bytes
コンパイル時間 1,629 ms
コンパイル使用メモリ 112,728 KB
実行使用メモリ 34,852 KB
最終ジャッジ日時 2024-04-14 10:33:46
合計ジャッジ時間 9,102 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
16,208 KB
testcase_01 AC 6 ms
14,036 KB
testcase_02 AC 5 ms
14,160 KB
testcase_03 AC 5 ms
14,044 KB
testcase_04 AC 6 ms
14,044 KB
testcase_05 AC 5 ms
14,164 KB
testcase_06 AC 5 ms
16,076 KB
testcase_07 AC 246 ms
30,500 KB
testcase_08 AC 244 ms
30,748 KB
testcase_09 AC 243 ms
30,744 KB
testcase_10 AC 242 ms
30,680 KB
testcase_11 AC 241 ms
30,892 KB
testcase_12 AC 242 ms
30,652 KB
testcase_13 AC 242 ms
30,672 KB
testcase_14 AC 248 ms
30,828 KB
testcase_15 AC 245 ms
30,744 KB
testcase_16 AC 245 ms
30,548 KB
testcase_17 AC 247 ms
30,744 KB
testcase_18 AC 245 ms
30,792 KB
testcase_19 AC 250 ms
30,636 KB
testcase_20 AC 255 ms
30,612 KB
testcase_21 AC 247 ms
31,608 KB
testcase_22 AC 251 ms
33,664 KB
testcase_23 AC 248 ms
34,852 KB
testcase_24 AC 252 ms
33,688 KB
testcase_25 AC 249 ms
34,764 KB
testcase_26 AC 252 ms
33,784 KB
testcase_27 AC 251 ms
34,616 KB
testcase_28 AC 251 ms
34,612 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target ("avx")

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> void chmin(T &t, const T &f) { if (t > f) t = f; }
template <class T> void chmax(T &t, const T &f) { if (t < f) t = f; }

template <class T, class S> struct SegmentTree {
  using OpTT = std::function<T(const T &, const T &)>;
  using OpSS = std::function<S(const S &, const S &)>;
  using OpST = std::function<T(const S &, const T &, int)>;
  const OpTT opTT;
  const OpSS opSS;
  const OpST opST;
  const T idT;
  const S idS;

  int n;
  vector<T> ts;
  vector<S> ss;
  SegmentTree(int n_, const OpTT opTT, const OpSS opSS, const OpST opST, const T &idT, const S &idS)
      : opTT(opTT), opSS(opSS), opST(opST), idT(idT), idS(idS) {
    for (n = 1; n < n_; n <<= 1) {}
    ts.assign(n << 1, idT);
    ss.assign(n << 1, idS);
  }
  T &at(int a) {
    return ts[n + a];
  }
  void build() {
    for (int a = n; --a; ) ts[a] = opTT(ts[a << 1], ts[a << 1 | 1]);
  }
  T query(int a, int b, const S &s) {
    return query(1, 0, n, a, b, s);
  }

 private:
  T query(int u, int l, int r, int a, int b, const S &s) {
    if (a < l) a = l;
    if (b > r) b = r;
    if (a >= b) return idT;
    if (a == l && b == r) {
      ts[u] = opST(s, ts[u], r - l);
      ss[u] = opSS(s, ss[u]);
      return ts[u];
    }
    const int uL = u << 1, uR = u << 1 | 1;
    const int mid = (l + r) >> 1;
    {
      ts[uL] = opST(ss[u], ts[uL], mid - l);
      ts[uR] = opST(ss[u], ts[uR], r - mid);
      ss[uL] = opSS(ss[u], ss[uL]);
      ss[uR] = opSS(ss[u], ss[uR]);
      ss[u] = idS;
    }
    const T resL = query(uL, l, mid, a, b, s);
    const T resR = query(uR, mid, r, a, b, s);
    ts[u] = opTT(ts[uL], ts[uR]);
    return opTT(resL, resR);
  }
};

struct T {
  Int sum, neg;
};
T opTT(const T &ta, const T &tb) {
  return T{ta.sum + tb.sum, ta.neg + tb.neg};
}
Int opSS(const Int &sa, const Int &sb) {
  return sa + sb;
}
T opST(const Int &s, const T &t, int sz) {
  return T{t.sum + ((sz - t.neg) - t.neg) * s, t.neg};
}
constexpr T idT{0, 0};


constexpr int MAX = 200010;

int N;
int U[MAX], V[MAX];
Int W[MAX];
int Q;
int TYP[MAX], A[MAX];
Int X[MAX];

vector<int> G[MAX];
int par[MAX];
int zeit, dis[MAX], fin[MAX];

void dfs(int u, int p) {
  par[u] = p;
  dis[u] = zeit++;
  for (const int i : G[u]) {
    const int v = U[i] ^ V[i] ^ u;
    if (v != p) {
      dfs(v, u);
    }
  }
  fin[u] = zeit++;
}

int main() {
  for (; ~scanf("%d", &N); ) {
    for (int i = 0; i < N - 1; ++i) {
      scanf("%d%d%lld", &U[i], &V[i], &W[i]);
    }
    scanf("%d", &Q);
    for (int q = 0; q < Q; ++q) {
      scanf("%d%d", &TYP[q], &A[q]);
      if (TYP[q] == 1) {
        scanf("%lld", &X[q]);
      }
    }
    
    for (int u = 0; u < N; ++u) {
      G[u].clear();
    }
    for (int i = 0; i < N - 1; ++i) {
      G[U[i]].push_back(i);
      G[V[i]].push_back(i);
    }
    zeit = 0;
    dfs(0, -1);
// cerr<<"dis = ";pv(dis,dis+N);
// cerr<<"fin = ";pv(fin,fin+N);
    
    SegmentTree<T, Int> seg(2 * N, opTT, opSS, opST, idT, 0);
    for (int i = 0; i < N - 1; ++i) {
      int u = U[i], v = V[i];
      if (par[u] == v) {
        swap(u, v);
      }
      seg.at(dis[v]) = T{W[i], 0};
      seg.at(fin[v]) = T{-W[i], 1};
    }
    seg.build();
// for(int m=1;m<=seg.n;m<<=1){for(int a=m;a<m<<1;++a){cerr<<"("<<seg.ts[a].sum<<", "<<seg.ts[a].neg<<") ";}cerr<<endl;}
    for (int q = 0; q < Q; ++q) {
      if (TYP[q] == 1) {
        seg.query(dis[A[q]] + 1, fin[A[q]], X[q]);
      } else {
        const T res = seg.query(0, dis[A[q]] + 1, 0);
        printf("%lld\n", res.sum);
      }
    }
  }
  return 0;
}
0