#ifndef LOCAL #define FAST_IO #endif // ============ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define OVERRIDE(a, b, c, d, ...) d #define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i) #define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i) #define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__) #define PER(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i) #define ALL(x) begin(x), end(x) using namespace std; using u32 = unsigned int; using u64 = unsigned long long; using i32 = signed int; using i64 = signed long long; using f64 = double; using f80 = long double; template using Vec = vector; template bool chmin(T &x, const T &y) { if (x > y) { x = y; return true; } return false; } template bool chmax(T &x, const T &y) { if (x < y) { x = y; return true; } return false; } #ifdef INT128 using u128 = __uint128_t; using i128 = __int128_t; istream &operator>>(istream &is, i128 &x) { i64 v; is >> v; x = v; return is; } ostream &operator<<(ostream &os, i128 x) { os << (i64)x; return os; } istream &operator>>(istream &is, u128 &x) { u64 v; is >> v; x = v; return is; } ostream &operator<<(ostream &os, u128 x) { os << (u64)x; return os; } #endif [[maybe_unused]] constexpr i32 INF = 1000000100; [[maybe_unused]] constexpr i64 INF64 = 3000000000000000100; struct SetUpIO { SetUpIO() { #ifdef FAST_IO ios::sync_with_stdio(false); cin.tie(nullptr); #endif cout << fixed << setprecision(15); } } set_up_io; // ============ #ifdef DEBUGF #else #define DBG(x) (void)0 #endif // ============ #include #include #include #include class HeavyLightDecomposition { std::vector siz; std::vector par; std::vector hea; std::vector in; std::vector out; std::vector dep; std::vector rev; template void dfs1(G &g, int v) { if (!g[v].empty() && (int) g[v][0] == par[v]) { std::swap(g[v][0], g[v].back()); } for (auto &e : g[v]) { int u = (int)e; if (u != par[v]) { par[u] = v; dfs1(g, u); siz[v] += siz[u]; if (siz[u] > siz[(int) g[v][0]]) { std::swap(g[v][0], e); } } } } template void dfs2(const G &g, int v, int &time) { in[v] = time; rev[time++] = v; for (auto &e : g[v]) { int u = (int)e; if (u == par[v]) { continue; } if (u == (int) g[v][0]) { hea[u] = hea[v]; } else { hea[u] = u; } dep[u] = dep[v] + 1; dfs2(g, u, time); } out[v] = time; } public: template HeavyLightDecomposition(G &g, int root = 0) : siz(g.size(), 1), par(g.size(), root), hea(g.size(), root), in(g.size(), 0), out(g.size(), 0), dep(g.size(), 0), rev(g.size(), 0) { assert(root >= 0 && root < (int) g.size()); dfs1(g, root); int time = 0; dfs2(g, root, time); } int subtree_size(int v) const { assert(v >= 0 && v < (int) siz.size()); return siz[v]; } int parent(int v) const { assert(v >= 0 && v < (int) par.size()); return par[v]; } int in_time(int v) const { assert(v >= 0 && v < (int) in.size()); return in[v]; } int out_time(int v) const { assert(v >= 0 && v < (int) out.size()); return out[v]; } int depth(int v) const { assert(v >= 0 && v < (int) dep.size()); return dep[v]; } int time_to_vertex(int t) const { assert(t >= 0 && t < (int) rev.size()); return rev[t]; } int la(int v, int k) const { assert(v >= 0 && v < (int) dep.size()); assert(k >= 0); if (k > dep[v]) { return -1; } while (true) { int u = hea[v]; if (in[u] + k <= in[v]) { return rev[in[v] - k]; } k -= in[v] - in[u] + 1; v = par[u]; } return 0; } int forward(int v, int dst) const { assert(v >= 0 && v < (int) dep.size()); assert(dst >= 0 && dst < (int) dep.size()); assert(v != dst); int l = lca(v, dst); if (l == v) { return la(dst, dep[dst] - dep[v] - 1); } else { return par[v]; } } int lca(int u, int v) const { assert(u >= 0 && u < (int) dep.size()); assert(v >= 0 && v < (int) dep.size()); while (u != v) { if (in[u] > in[v]) { std::swap(u, v); } if (hea[u] == hea[v]) { v = u; } else { v = par[hea[v]]; } } return u; } int dist(int u, int v) const { assert(u >= 0 && u < (int) dep.size()); assert(v >= 0 && v < (int) dep.size()); return dep[u] + dep[v] - 2 * dep[lca(u, v)]; } std::vector> path(int u, int v, bool edge) const { assert(u >= 0 && u < (int) dep.size()); assert(v >= 0 && v < (int) dep.size()); std::vector> fromu, fromv; bool rev = false; while (true) { if (u == v && edge) { break; } if (in[u] > in[v]) { std::swap(u, v); std::swap(fromu, fromv); rev ^= true; } if (hea[u] == hea[v]) { fromv.emplace_back(in[v], in[u] + (int)edge); v = u; break; } else { fromv.emplace_back(in[v], in[hea[v]]); v = par[hea[v]]; } } if (rev) { std::swap(fromu, fromv); } std::reverse(fromv.begin(), fromv.end()); fromu.reserve(fromv.size()); for (auto [x, y] : fromv) { fromu.emplace_back(y, x); } return fromu; } int jump(int u, int v, int k) const { assert(u >= 0 && u < (int) dep.size()); assert(v >= 0 && v < (int) dep.size()); assert(k >= 0); int l = lca(u, v); int dis = dep[u] + dep[v] - 2 * dep[l]; if (k > dis) { return -1; } if (k <= dep[u] - dep[l]) { return la(u, k); } else { return la(v, dis - k); } } int meet(int u, int v, int w) const { return lca(u, v) ^ lca(v, w) ^ lca(w, u); } }; // ============ // ============ #include #include #include template class LazySegmentTree { public: using Value = typename MonoidFunc::Value; using Func = typename MonoidFunc::Func; private: int old_length; int lg; int length; std::vector values; std::vector funcs; static int lg2(int n) { int x = 1; int l = 0; while (x < n) { x <<= 1; ++l; } return l; } void _apply(int idx, const Func &func) { values[idx] = MonoidFunc::apply(func, values[idx]); funcs[idx] = MonoidFunc::composite(func, funcs[idx]); } void push(int idx) { _apply(idx << 1, funcs[idx]); _apply(idx << 1 | 1, funcs[idx]); funcs[idx] = MonoidFunc::func_id(); } void recalc_values(int idx) { values[idx] = MonoidFunc::op(values[idx << 1], values[idx << 1 | 1]); } public: LazySegmentTree(int n) : old_length(n), lg(lg2(n)), length(1 << lg), values(length << 1, MonoidFunc::id()), funcs(length << 1, MonoidFunc::func_id()) { assert(n >= 0); } LazySegmentTree(const std::vector &v) : old_length((int) v.size()), lg(lg2(old_length)), length(1 << lg), values(length << 1, MonoidFunc::id()), funcs(length << 1, MonoidFunc::func_id()) { for (int i = 0; i < old_length; ++i) { values[i + length] = v[i]; } for (int i = length - 1; i > 0; --i) { recalc_values(i); } } template LazySegmentTree(int n, const F &f) : old_length(n), lg(lg2(n)), length(1 << lg), values(length << 1, MonoidFunc::id()), funcs(length << 1, MonoidFunc::func_id()) { for (int i = 0; i < old_length; ++i) { values[i + length] = f(i); } for (int i = length - 1; i > 0; --i) { recalc_values(i); } } void update(int idx, Value val) { assert(idx >= 0 && idx < old_length); idx += length; for (int i = lg; i > 0; --i) { push(idx >> i); } values[idx] = std::move(val); while (idx >>= 1) { recalc_values(idx); } } void apply(int l, int r, const Func &func) { assert(l >= 0 && l <= r && r <= old_length); if (l == r) { return; } l += length; r += length; int _l = l; int _r = r; for (int i = lg; i > 0; --i) { push(_l >> i); push((_r - 1) >> i); } while (l < r) { if (l & 1) { _apply(l++, func); } if (r & 1) { _apply(--r, func); } l >>= 1; r >>= 1; } for (int i = 1; i <= lg; ++i) { if ((_l >> i << i) != _l) { recalc_values(_l >> i); } if ((_r >> i << i) != _r) { recalc_values((_r - 1) >> i); } } } Value prod(int l, int r) { assert(l >= 0 && l <= r && r <= old_length); if (l == r) { return MonoidFunc::id(); } l += length; r += length; for (int i = lg; i > 0; --i) { push(l >> i); push((r - 1) >> i); } Value lp = MonoidFunc::id(); Value rp = MonoidFunc::id(); while (l < r) { if (l & 1) { lp = MonoidFunc::op(lp, values[l++]); } if (r & 1) { rp = MonoidFunc::op(values[--r], rp); } l >>= 1; r >>= 1; } return MonoidFunc::op(lp, rp); } Value all_prod() const { return values[1]; } }; // ============ // ============ #include #include // ============ #include #include template struct Add { using Value = T; static Value id() { return T(0); } static Value op(const Value &lhs, const Value &rhs) { return lhs + rhs; } static Value inv(const Value &x) { return -x; } }; template struct Mul { using Value = T; static Value id() { return Value(1); } static Value op(const Value &lhs, const Value &rhs) { return lhs * rhs; } static Value inv(const Value &x) { return Value(1) / x; } }; template struct Min { using Value = T; static Value id() { return std::numeric_limits::max(); } static Value op(const Value &lhs, const Value &rhs) { return std::min(lhs, rhs); } }; template struct Max { using Value = T; static Value id() { return std::numeric_limits::min(); } static Value op(const Value &lhs, const Value &rhs) { return std::max(lhs, rhs); } }; template struct Xor { using Value = T; static Value id() { return T(0); } static Value op(const Value &lhs, const Value &rhs) { return lhs ^ rhs; } static Value inv(const Value &x) { return x; } }; template struct Reversible { using Value = std::pair; static Value id() { return Value(Monoid::id(), Monoid::id()); } static Value op(const Value &v1, const Value &v2) { return Value( Monoid::op(v1.first, v2.first), Monoid::op(v2.second, v1.second)); } }; // ============ template class FenwickTree { public: using Value = typename CommutativeGroup::Value; private: std::vector data; public: FenwickTree(int n) : data(n, CommutativeGroup::id()) {} void add(int idx, const Value &x) { assert(idx >= 0 && idx < (int) data.size()); for (; idx < (int) data.size(); idx |= idx + 1) { data[idx] = CommutativeGroup::op(data[idx], x); } } Value sum(int r) const { assert(r >= 0 && r <= (int) data.size()); Value ret = CommutativeGroup::id(); for (; r > 0; r &= r - 1) { ret = CommutativeGroup::op(ret, data[r - 1]); } return ret; } Value sum(int l, int r) const { assert(l >= 0 && l <= r && r <= (int) data.size()); return CommutativeGroup::op(sum(r), CommutativeGroup::inv(sum(l))); } }; template using FenwickTreeAdd = FenwickTree>; // ============ struct Ops { using Value = pair; using Func = i64; static Value id() { return Value(INF64, -1); } static Value op(Value x, Value y) { if (x.first > y.first) { swap(x, y); } if (y.first <= 0) { return x.second > y.second ? x : y; } else { return x; } } static Func func_id() { return 0; } static Func composite(Func f, Func g) { return f + g; } static Value apply(Func f, Value x) { return Value(x.first + f, x.second); } }; struct RAPS { FenwickTreeAdd fw; RAPS(i32 n) : fw(n + 1) {} void add(i32 l, i32 r, i32 v) { fw.add(l, v); fw.add(r, -v); } i32 get(i32 x) { return fw.sum(x + 1); } }; int main() { i32 n, q; cin >> n >> q; Vec a(n - 1), b(n - 1); Vec c(n - 1); REP(i, n - 1) { cin >> a[i] >> b[i] >> c[i]; --a[i]; --b[i]; } Vec> tree(n); REP(i, n - 1) { tree[a[i]].push_back(b[i]); tree[b[i]].push_back(a[i]); } HeavyLightDecomposition hld(tree); RAPS sz(n); REP(i, n) { sz.add(i, i + 1, hld.subtree_size(hld.time_to_vertex(i))); } LazySegmentTree seg(n); Vec def(n, 0); REP(i, n - 1) { if (a[i] == hld.parent(b[i])) { seg.update(hld.in_time(b[i]), Ops::Value(c[i], hld.in_time(b[i]))); def[b[i]] = c[i]; } else { seg.update(hld.in_time(a[i]), Ops::Value(c[i], hld.in_time(a[i]))); def[a[i]] = c[i]; } } while (q--) { i32 type; cin >> type; if (type == 1) { i32 v; i64 x; cin >> v >> x; --v; for (auto [l, r] : hld.path(0, v, true)) { ++r; seg.apply(l, r, -x); } Ops::Value val = seg.all_prod(); if (val.first <= 0) { i32 u = hld.time_to_vertex(val.second); i64 apple = def[u] - val.first; for (auto [l, r] : hld.path(0, hld.parent(u), true)) { ++r; seg.apply(l, r, apple); } for (auto [l, r] : hld.path(0, hld.parent(u), false)) { ++r; sz.add(l, r, -sz.get(val.second)); } seg.apply(hld.in_time(u), hld.out_time(u), apple); } } else { cout << sz.get(0) << '\n'; } /*REP(i, n) { Ops::Value val = seg.prod(i, i + 1); cout << "v = " << hld.time_to_vertex(i) << ", val = (" << val.first << ", " << val.second << ")\n"; }*/ } }