#include // clang-format off std::ostream&operator<<(std::ostream&os,std::int8_t x){return os<<(int)x;} std::ostream&operator<<(std::ostream&os,std::uint8_t x){return os<<(int)x;} std::ostream&operator<<(std::ostream&os,const __int128_t &v){if(!v)os<<"0";__int128_t tmp=v<0?(os<<"-",-v):v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<std::ostream &operator<<(std::ostream&,const std::vector&); templatestd::ostream &operator<<(std::ostream&,const std::set&); templatestd::ostream &operator<<(std::ostream&os,const std::pair&x){return os<<"("<std::ostream&operator<<(std::ostream &os,const std::array &arr) {os<<'['<void print(std::ostream&os,const Tup &x,std::index_sequence){(void)(int[]){(os<(x)<<", ",0)...};} templatestd::ostream &operator<<(std::ostream&os,const std::tuple &x) {static constexpr std::size_t N = sizeof...(Args);os<<"(";if constexpr(N>=2)print(os,x,std::make_index_sequence());return os<(x)<<")";} templatestd::ostream &operator<<(std::ostream&os,const std::vector&vec){os<<'[';for(int _=0,__= vec.size();_<__;++_)os<<(_ ?", ":"")<std::ostream &operator<<(std::ostream&os,const std::set&s){os<<'{';int _=0;for(const auto &x:s)os<<(_++ ? ", " : "")<"< void debug__(const std::string &s, const T &a, const Args &...x) {std::cerr << BRIGHT_CYAN << s << COLOR_RESET << " = ";std::cerr << a;(std::cerr << ... << (std::cerr << ", ", x));std::cerr << func_LINE_FILE << std::endl;} #define debug(...) debug__(#__VA_ARGS__,__VA_ARGS__) #define debugArray(x, n) do{std::cerr< static constexpr bool tuple_like_v= false; template static constexpr bool tuple_like_v> = true; template static constexpr bool tuple_like_v> = true; template static constexpr bool tuple_like_v> = true; template auto to_tuple(const T &t) { if constexpr (tuple_like_v) return std::apply([](auto &&...x) { return std::make_tuple(x...); }, t); } template auto forward_tuple(const T &t) { if constexpr (tuple_like_v) return std::apply([](auto &&...x) { return std::forward_as_tuple(x...); }, t); } template static constexpr bool array_like_v= false; template static constexpr bool array_like_v> = true; template static constexpr bool array_like_v> = std::is_convertible_v; template static constexpr bool array_like_v> = true; template static constexpr bool array_like_v> = array_like_v> && std::is_convertible_v; template auto to_array(const T &t) { if constexpr (array_like_v) return std::apply([](auto &&...x) { return std::array{x...}; }, t); } template using to_tuple_t= decltype(to_tuple(T())); template using to_array_t= decltype(to_array(T())); template class SegmentTree_2D { public: using T= typename M::T; using Pos= std::array; std::vector xs; std::vector yxs; std::vector id, tol; std::vector val; template using canbe_Pos= std::is_convertible, std::tuple>; template using canbe_PosV= std::is_convertible, std::tuple>; template static constexpr bool canbe_Pos_and_T_v= std::conjunction_v, std::is_convertible>; int sz; inline int x2i(pos_t x) const { return std::lower_bound(xs.begin(), xs.end(), x) - xs.begin(); } inline int y2i(pos_t y) const { return std::lower_bound(yxs.begin(), yxs.end(), Pos{y, 0}, [](const Pos &a, const Pos &b) { return a[0] < b[0]; }) - yxs.begin(); } inline int xy2i(pos_t x, pos_t y) const { Pos p{y, x}; auto it= std::lower_bound(yxs.begin(), yxs.end(), p); return assert(p == *it), it - yxs.begin(); } template inline auto get_(const P &p) { if constexpr (z) return std::get(p); else return std::get(p.first); } template inline void build(const XYW *xyw, int n, const T &v= M::ti()) { xs.resize(n), yxs.resize(n); for (int i= n; i--;) xs[i]= get_(xyw[i]); std::sort(xs.begin(), xs.end()), xs.erase(std::unique(xs.begin(), xs.end()), xs.end()), id.resize((sz= 1 << (32 - __builtin_clz(xs.size()))) * 2 + 1); std::vector ix(n), ord(n); for (int i= n; i--;) ix[i]= x2i(get_(xyw[i])); for (int i: ix) for (i+= sz; i; i>>= 1) ++id[i + 1]; for (int i= 1, e= sz * 2; i < e; ++i) id[i + 1]+= id[i]; val.assign(id.back() * 2, M::ti()), tol.resize(id[sz] + 1), std::iota(ord.begin(), ord.end(), 0), std::sort(ord.begin(), ord.end(), [&](int i, int j) { return get_(xyw[i]) == get_(xyw[j]) ? get_(xyw[i]) < get_(xyw[j]) : get_(xyw[i]) < get_(xyw[j]); }); for (int i= n; i--;) yxs[i]= {get_(xyw[ord[i]]), get_(xyw[ord[i]])}; std::vector ptr= id; for (int r: ord) for (int i= ix[r] + sz, j= -1; i; j= i, i>>= 1) { int p= ptr[i]++; if constexpr (z) { if constexpr (std::tuple_size_v == 3) val[id[i + 1] + p]= std::get<2>(xyw[r]); else val[id[i + 1] + p]= v; } else val[id[i + 1] + p]= xyw[r].second; if (j != -1) tol[p + 1]= !(j & 1); } for (int i= 1, e= id[sz]; i < e; ++i) tol[i + 1]+= tol[i]; for (int i= 0, e= sz * 2; i < e; ++i) { auto dat= val.begin() + id[i] * 2; for (int j= id[i + 1] - id[i]; --j > 0;) dat[j]= M::op(dat[j * 2], dat[j * 2 + 1]); } } inline T fold(int i, int a, int b) const { int n= id[i + 1] - id[i]; T ret= M::ti(); auto dat= val.begin() + id[i] * 2; for (a+= n, b+= n; a < b; a>>= 1, b>>= 1) { if (a & 1) ret= M::op(ret, dat[a++]); if (b & 1) ret= M::op(dat[--b], ret); } return ret; } template inline void seti(int i, int j, T v) { auto dat= val.begin() + id[i] * 2; j+= id[i + 1] - id[i]; if constexpr (z) dat[j]= v; else dat[j]= M::op(dat[j], v); for (; j;) j>>= 1, dat[j]= M::op(dat[2 * j], dat[2 * j + 1]); } template inline void set_(pos_t x, pos_t y, T v) { for (int i= 1, p= xy2i(x, y);;) { if (seti(i, p - id[i], v); i >= sz) break; if (int lc= tol[p] - tol[id[i]], rc= (p - id[i]) - lc; tol[p + 1] - tol[p]) p= id[2 * i] + lc, i= 2 * i; else p= id[2 * i + 1] + rc, i= 2 * i + 1; } } public: template , canbe_PosV

>>> SegmentTree_2D(const P *p, size_t n) { build<1>(p, n); } template , canbe_PosV

>>> SegmentTree_2D(const std::vector

&p): SegmentTree_2D(p.data(), p.size()) {} template ::value>> SegmentTree_2D(const std::set

&p): SegmentTree_2D(std::vector(p.begin(), p.end())) {} template >> SegmentTree_2D(const P *p, size_t n, const U &v) { build<1>(p, n, v); } template >> SegmentTree_2D(const std::vector

&p, const U &v): SegmentTree_2D(p.data(), p.size(), v) {} template >> SegmentTree_2D(const std::set

&p, const U &v): SegmentTree_2D(std::vector(p.begin(), p.end()), v) {} template >> SegmentTree_2D(const std::pair *p, size_t n) { build<0>(p, n); } template >> SegmentTree_2D(const std::vector> &p): SegmentTree_2D(p.data(), p.size()) {} template >> SegmentTree_2D(const std::map &p): SegmentTree_2D(std::vector(p.begin(), p.end())) {} // [l,r) x [u,d) T fold(pos_t l, pos_t r, pos_t u, pos_t d) const { T ret= M::ti(); int L= x2i(l), R= x2i(r); auto dfs= [&](auto &dfs, int i, int a, int b, int c, int d) -> void { if (c == d || R <= a || b <= L) return; if (L <= a && b <= R) return ret= M::op(ret, fold(i, c, d)), void(); int m= (a + b) / 2, ac= tol[id[i] + c] - tol[id[i]], bc= c - ac, ad= tol[id[i] + d] - tol[id[i]], bd= d - ad; dfs(dfs, i * 2, a, m, ac, ad), dfs(dfs, i * 2 + 1, m, b, bc, bd); }; return dfs(dfs, 1, 0, sz, y2i(u), y2i(d)), ret; } void set(pos_t x, pos_t y, T v) { set_<1>(x, y, v); } void mul(pos_t x, pos_t y, T v) { set_<0>(x, y, v); } T get(pos_t x, pos_t y) const { return val[xy2i(x, y) + id[2]]; } }; template struct ListRange { using Iterator= typename std::vector::const_iterator; Iterator bg, ed; Iterator begin() const { return bg; } Iterator end() const { return ed; } size_t size() const { return std::distance(bg, ed); } const T &operator[](int i) const { return bg[i]; } }; template class CsrArray { std::vector csr; std::vector pos; public: CsrArray()= default; CsrArray(const std::vector &c, const std::vector &p): csr(c), pos(p) {} size_t size() const { return pos.size() - 1; } const ListRange operator[](int i) const { return {csr.cbegin() + pos[i], csr.cbegin() + pos[i + 1]}; } }; template class Tree { template struct Edge_B { int to; T cost; operator int() const { return to; } }; template struct Edge_B { int to; operator int() const { return to; } }; using Edge= Edge_B; using C= std::conditional_t, std::nullptr_t, Cost>; std::vector, std::pair, std::tuple>> es; std::vector g; std::vector P, PP, D, I, L, R, pos; std::vector DW, W; public: Tree(int n): P(n, -2) {} template std::enable_if_t, void> add_edge(int u, int v) { es.emplace_back(u, v), es.emplace_back(v, u); } template std::enable_if_t, void> add_edge(int u, int v, T c) { es.emplace_back(u, v, c), es.emplace_back(v, u, c); } template , std::is_convertible>, std::nullptr_t> = nullptr> void add_edge(int u, int v, T c, U d) /* c:u->v, d:v->u */ { es.emplace_back(u, v, c), es.emplace_back(v, u, d); } void build(int root= 0) { size_t n= P.size(); I.resize(n), PP.resize(n), std::iota(PP.begin(), PP.end(), 0), D.assign(n, 0), L.assign(n, 0), R.assign(n, 0), pos.resize(n + 1), g.resize(es.size()); for (const auto &e: es) ++pos[std::get<0>(e)]; std::partial_sum(pos.begin(), pos.end(), pos.begin()); if constexpr (std::is_void_v) for (const auto &[f, t]: es) g[--pos[f]]= {t}; else for (const auto &[f, t, c]: es) g[--pos[f]]= {t, c}; auto f= [&, i= 0, v= 0, t= 0](int r) mutable { for (P[r]= -1, I[t++]= r; i < t; ++i) for (int u: operator[](v= I[i])) if (P[v] != u) P[I[t++]= u]= v; }; f(root); for (size_t r= 0; r < n; ++r) if (P[r] == -2) f(r); std::vector Z(n, 1), nx(n, -1); for (int i= n, v; i--;) { if (P[v= I[i]] == -1) continue; if (Z[P[v]]+= Z[v]; nx[P[v]] == -1) nx[P[v]]= v; if (Z[nx[P[v]]] < Z[v]) nx[P[v]]= v; } for (int v: I) if (nx[v] != -1) PP[nx[v]]= v; for (int v: I) if (P[v] != -1) PP[v]= PP[PP[v]], D[v]= D[P[v]] + 1; for (int i= n; i--;) L[I[i]]= i; for (int v: I) { int ir= R[v]= L[v] + Z[v]; for (int u: operator[](v)) if (u != P[v] && u != nx[v]) L[u]= ir-= Z[u]; if (nx[v] != -1) L[nx[v]]= L[v] + 1; } if constexpr (weight) { DW.resize(n), W.resize(n); for (int v: I) for (auto &[u, c]: operator[](v)) { if (u != P[v]) DW[u]= DW[v] + c; else W[v]= c; } } for (int i= n; i--;) I[L[i]]= i; } size_t size() const { return P.size(); } const ListRange operator[](int v) const { return {g.cbegin() + pos[v], g.cbegin() + pos[v + 1]}; } int depth(int v) const { return D[v]; } C depth_w(int v) const { static_assert(weight, "\'depth_w\' is not available"); return DW[v]; } int to_seq(int v) const { return L[v]; } int to_node(int i) const { return I[i]; } int parent(int v) const { return P[v]; } int root(int v) const { for (v= PP[v];; v= PP[P[v]]) if (P[v] == -1) return v; } bool connected(int u, int v) const { return root(u) == root(v); } int lca(int u, int v) const { for (;; v= P[PP[v]]) { if (L[u] > L[v]) std::swap(u, v); if (PP[u] == PP[v]) return u; } } int la(int v, int k) const { assert(k <= D[v]); for (int u;; k-= L[v] - L[u] + 1, v= P[u]) if (L[v] - k >= L[u= PP[v]]) return I[L[v] - k]; } int la_w(int v, Cost w) const { static_assert(weight, "\'la_w\' is not available"); for (Cost c;; w-= c) { int u= PP[v]; c= DW[v] - DW[u] + W[u]; if (w < c) { int ok= L[v], ng= L[u] - 1; while (ok - ng > 1) { if (int m= (ok + ng) / 2; DW[v] - DW[I[m]] <= w) ok= m; else ng= m; } return I[ok]; } if (v= P[u]; v == -1) return u; } } int jump(int u, int v, int k) const { if (!k) return u; if (u == v) return -1; if (k == 1) return in_subtree(v, u) ? la(v, D[v] - D[u] - 1) : P[u]; int w= lca(u, v), d_uw= D[u] - D[w], d_vw= D[v] - D[w]; return k > d_uw + d_vw ? -1 : k <= d_uw ? la(u, k) : la(v, d_uw + d_vw - k); } int jump_w(int u, int v, Cost w) const { static_assert(weight, "\'jump_w\' is not available"); if (u == v) return u; int z= lca(u, v); Cost d_uz= DW[u] - DW[z], d_vz= DW[v] - DW[z]; return w >= d_uz + d_vz ? v : w <= d_uz ? la_w(u, w) : la_w(v, d_uz + d_vz - w); } int dist(int u, int v) const { return D[u] + D[v] - D[lca(u, v)] * 2; } C dist_w(int u, int v) const { static_assert(weight, "\'dist_w\' is not available"); return DW[u] + DW[v] - DW[lca(u, v)] * 2; } // u is in v bool in_subtree(int u, int v) const { return L[v] <= L[u] && L[u] < R[v]; } int subtree_size(int v) const { return R[v] - L[v]; } // half-open interval std::array subtree(int v) const { return std::array{L[v], R[v]}; } // sequence of closed intervals template std::vector> path(int u, int v) const { std::vector> up, down; while (PP[u] != PP[v]) { if (L[u] < L[v]) down.emplace_back(std::array{L[PP[v]], L[v]}), v= P[PP[v]]; else up.emplace_back(std::array{L[u], L[PP[u]]}), u= P[PP[u]]; } if (L[u] < L[v]) down.emplace_back(std::array{L[u] + edge, L[v]}); else if (L[v] + edge <= L[u]) up.emplace_back(std::array{L[u], L[v] + edge}); return up.insert(up.end(), down.rbegin(), down.rend()), up; } }; using namespace std; struct RSQ { using T= int; static T ti() { return 0; } static T op(T l, T r) { return l + r; } }; signed main() { cin.tie(0); ios::sync_with_stdio(0); int N, Q; cin >> N >> Q; debug(N, Q); Tree tree(N); for (int i= 1; i < N; ++i) { int A, B, C; cin >> A >> B >> C; tree.add_edge(--A, --B, C); } tree.build(0); set> st; vector> query; for (int i= 0; i < Q; ++i) { int tp, v, t, l; cin >> tp >> v >> t >> l, --v; if (tp == 0) { int x= tree.to_seq(v), y= t + tree.depth_w(v); query.emplace_back(1, 0, x, y); st.insert({x, y}); // debug(v, l, tree.la_w(v, l)); if (int u= tree.parent(tree.la_w(v, l)); u != -1) { debug(v, u); x= tree.to_seq(u); query.emplace_back(-1, 0, x, y); st.insert({x, y}); } } else { auto [l, r]= tree.subtree(v); query.emplace_back(0, l, r, t + tree.depth_w(v)); } } SegmentTree_2D seg(st); for (auto [t, a, b, y]: query) { if (t == 0) cout << seg.fold(a, b, 0, y + 1) << '\n'; else seg.mul(b, y, t); } return 0; }