結果

問題 No.900 aδδitivee
ユーザー 👑 hos.lyrichos.lyric
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0