// #ifdef ONLINE_JUDGE #pragma GCC optimize("Ofast") #pragma GCC target("avx2,bmi,bmi2,lzcnt") // #endif #include #include #ifndef DUMP #define DUMP(...) void(0) #endif using namespace std; struct graph { struct edge { int src, dst; int64_t cost; int operator-(int v) const { return src ^ dst ^ v; } }; int n, m; vector edges; vector>> adj; graph(int _n = 0) : n(_n), m(0), adj(n) {} int add(const edge& e, bool directed = false) { edges.push_back(e); adj[e.src].emplace_back(m, e.dst); if (not directed) adj[e.dst].emplace_back(m, e.src); return m++; } }; struct dfs_forest : graph { using T = decltype(edge::cost); vector root, pv, pe, sz, dep, min_dep, last, ord, in, out; vector dist; int trials; dfs_forest(int _n = 0) : graph(_n), dist(n), trials(0) { for (auto p : {&root, &pv, &pe, &sz, &dep, &min_dep, &last, &in, &out}) p->assign(n, -1); } int add(const edge& e) { return graph::add(e); } void dfs(int v) { sz[v] = 1, min_dep[v] = dep[v], last[v] = trials; in[v] = size(ord), ord.push_back(v); for (auto [id, u] : adj[v]) { if (id == pe[v]) continue; if (last[u] == trials) { min_dep[v] = min(min_dep[v], dep[u]); continue; } root[u] = root[v], pv[u] = v, pe[u] = id, dep[u] = dep[v] + 1; dist[u] = dist[v] + edges[id].cost; dfs(u); sz[v] += sz[u], min_dep[v] = min(min_dep[v], min_dep[u]); } out[v] = size(ord); } void build(int r, bool clear_ord = true) { root[r] = r, pv[r] = pe[r] = -1, dep[r] = 0, dist[r] = T{}; if (clear_ord) ord.clear(); dfs(r); ++trials; } void build() { fill(begin(root), end(root), -1); for (int v = 0; v < n; ++v) if (root[v] == -1) build(v, v == 0); } int farther(int id) const { int u = edges[id].src, v = edges[id].dst; return dep[u] < dep[v] ? v : u; } bool spans(int id) const { return id == pe[farther(id)]; } bool anc(int u, int v) const { return in[u] <= in[v] and out[v] <= out[u]; } }; template struct range2d { struct bit_vector { using size_type = uint32_t; static constexpr size_type wsize = 64; static size_type rank64(uint64_t x, size_type i) { return _popcnt64(_bzhi_u64(x, i)); } #pragma pack(4) struct block_t { uint64_t bit; size_type sum; }; #pragma pack() size_type n, zeros; vector block; bit_vector(size_type _n = 0) : n(_n), block(n / wsize + 1) {} int operator[](size_type i) const { return block[i / wsize].bit >> i % wsize & 1; } void set(size_type i) { block[i / wsize].bit |= (uint64_t)1 << i % wsize; } void build() { for (size_type j = 0; j < n / wsize; ++j) block[j + 1].sum = block[j].sum + _popcnt64(block[j].bit); zeros = rank0(n); } size_type rank0(size_type i) const { return i - rank1(i); } size_type rank1(size_type i) const { auto&& e = block[i / wsize]; return e.sum + rank64(e.bit, i % wsize); } }; struct fenwick { int n; vector t; fenwick(int _n = 0) : n(_n), t(n) {} void add(int i, T val) { for (++i; i <= n; i += _blsi_u64(i)) t[i - 1] += val; } T sum(int i) const { T res = 0; for (; i; i = _blsr_u64(i)) res += t[i - 1]; return res; } T sum(int l, int r) const { return sum(r) - sum(l); } }; using key_type = int64_t; int n, lg; vector bv; vector ft; vector> p; vector ys; void add_point(key_type x, key_type y) { p.emplace_back(x, y); ys.push_back(y); } void build() { sort(begin(p), end(p)); p.erase(unique(begin(p), end(p)), end(p)); n = size(p); sort(begin(ys), end(ys)); ys.erase(unique(begin(ys), end(ys)), end(ys)); vector a(n), na(n); for (int i = 0; i < n; ++i) a[i] = y2a(p[i].second); lg = __lg(max(*max_element(begin(a), end(a)), 1)) + 1; bv.assign(lg, n); ft.assign(lg + 1, n); for (auto h = lg; h--;) { for (int i = 0; i < n; ++i) if (a[i] >> h & 1) bv[h].set(i); bv[h].build(); array it{begin(na), begin(na) + bv[h].zeros}; for (int i = 0; i < n; ++i) *it[bv[h][i]]++ = a[i]; swap(a, na); } } int x2i(key_type x) const { pair t{x, numeric_limits::min()}; return lower_bound(begin(p), end(p), t) - begin(p); } int y2a(key_type y) const { return lower_bound(begin(ys), end(ys), y) - begin(ys); } void add(key_type x, key_type y, T val) { assert(binary_search(begin(p), end(p), pair{x, y})); int i = lower_bound(begin(p), end(p), pair{x, y}) - begin(p); ft[lg].add(i, val); for (int h = lg; h--;) { int i0 = bv[h].rank0(i); if (bv[h][i] == 0) i = i0; else i += bv[h].zeros - i0; ft[h].add(i, val); } } T sum(int l, int r, int ub) const { if (ub >= 1 << lg) return ft[lg].sum(l, r); T res = 0; for (int h = lg; h--;) { int l0 = bv[h].rank0(l), r0 = bv[h].rank0(r); if (~ub >> h & 1) l = l0, r = r0; else { res += ft[h].sum(l0, r0); l += bv[h].zeros - l0; r += bv[h].zeros - r0; } } return res; } T sum(key_type lx, key_type rx, key_type ly, key_type ry) const { int l = x2i(lx), r = x2i(rx); return sum(l, r, y2a(ry)) - sum(l, r, y2a(ly)); } }; int main() { cin.tie(nullptr)->sync_with_stdio(false); int n, q; cin >> n >> q; dfs_forest g(n); for (int _ = n - 1; _--;) { int u, v; int64_t w; cin >> u >> v >> w; --u, --v; g.add({u, v, w}); } g.build(); struct query { int type, v; int64_t t, l; }; vector queries(q); vector> ds(2 * n); for (auto&& [type, v, t, l] : queries) { cin >> type >> v >> t >> l; --v; DUMP(type, v, t, l); if (type == 0) { int i = g.in[v] + n; ds[i].add_point(t + g.dist[v], g.dist[v] - l); while (i >>= 1) ds[i].add_point(t + g.dist[v], g.dist[v] - l); } } for (auto&& e : ds) if (not empty(e.p)) e.build(); for (auto&& [type, v, t, l] : queries) { if (type == 0) { int i = g.in[v] + n; ds[i].add(t + g.dist[v], g.dist[v] - l, 1); while (i >>= 1) ds[i].add(t + g.dist[v], g.dist[v] - l, 1); } else if (type == 1) { int res = 0; for (int l = g.in[v] + n, r = g.out[v] + n; l < r; l >>= 1, r >>= 1) { if (l & 1) res += ds[l++].sum(-9e18, t + g.dist[v] + 1, -9e18, g.dist[v] + 1); if (r & 1) res += ds[--r].sum(-9e18, t + g.dist[v] + 1, -9e18, g.dist[v] + 1); } cout << res << '\n'; } else assert(false); } }