結果
問題 | No.900 aδδitivee |
ユーザー |
👑 |
提出日時 | 2019-10-04 21:53:25 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 254 ms / 2,000 ms |
コード長 | 4,348 bytes |
コンパイル時間 | 1,182 ms |
コンパイル使用メモリ | 112,796 KB |
実行使用メモリ | 34,552 KB |
最終ジャッジ日時 | 2024-10-03 07:31:34 |
合計ジャッジ時間 | 8,250 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 |
ソースコード
// #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;}