#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> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; } template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; } int N, Q; vector<int> A, B; vector<Int> C; vector<int> TYP, V; vector<Int> T, L; vector<vector<int>> G; vector<int> par, sz, dep; vector<Int> dist; int O; vector<int> ord, head; void dfs0(int u, int p, int ip) { par[u] = p; sz[u] = 1; dep[u] = (p == -1) ? 0 : (dep[p] + 1); dist[u] = (p == -1) ? 0 : (dist[p] + C[ip]); for (const int i : G[u]) { const int v = A[i] ^ B[i] ^ u; if (v != p) { dfs0(v, u, i); sz[u] += sz[v]; } } } void dfs1(int u, int p, int h) { ord[u] = O++; head[u] = h; int vm = -1; for (const int i : G[u]) { const int v = A[i] ^ B[i] ^ u; if (v != p) { if (vm == -1 || sz[vm] < sz[v]) { vm = v; } } } if (vm != -1) { dfs1(vm, u, h); for (const int i : G[u]) { const int v = A[i] ^ B[i] ^ u; if (v != p && v != vm) { dfs1(v, u, v); } } } } int BIT_N; struct BIT { map<int, int> as; void add(int pos, int val) { for (int x = pos; x < BIT_N; x |= x + 1) { as[x] += val; } } int sum(int pos) { int ret = 0; for (int x = pos - 1; x >= 0; x = (x & (x + 1)) - 1) { auto it = as.find(x); if (it != as.end()) { ret += it->second; } } return ret; } }; constexpr int E = 16; int main() { for (; ~scanf("%d%d", &N, &Q); ) { A.resize(N - 1); B.resize(N - 1); C.resize(N - 1); for (int i = 0; i < N - 1; ++i) { scanf("%d%d%lld", &A[i], &B[i], &C[i]); --A[i]; --B[i]; } TYP.resize(Q); V.resize(Q); T.resize(Q); L.resize(Q); for (int q = 0; q < Q; ++q) { scanf("%d%d%lld%lld", &TYP[q], &V[q], &T[q], &L[q]); --V[q]; } G.assign(N, {}); for (int i = 0; i < N - 1; ++i) { G[A[i]].push_back(i); G[B[i]].push_back(i); } par.resize(N); sz.resize(N); dep.resize(N); dist.resize(N); constexpr int rt = 0; dfs0(rt, -1, -1); O = 0; ord.resize(N); head.resize(N); dfs1(rt, -1, rt); // cerr<<"dist = ";pv(dist.begin(),dist.end()); // cerr<<"ord = ";pv(ord.begin(),ord.end()); // cerr<<"head = ";pv(head.begin(),head.end()); vector<int> lens(N, 0); for (int u = 0; u < N; ++u) { ++lens[head[u]]; } BIT_N = Q; vector<vector<BIT>> bits(N); for (int h = 0; h < N; ++h) { bits[h].assign(lens[h], {}); } auto bAdd = [&](int h, int pos, int key, int val) { // cerr<<"bAdd "<<h<<" "<<pos<<" "<<key<<" "<<val<<endl; for (int x = pos; x < lens[h]; x |= x + 1) { bits[h][x].add(key, val); } }; auto bSum = [&](int h, int pos, int key) { int ret = 0; for (int x = pos - 1; x >= 0; x = (x & (x + 1)) - 1) { ret += bits[h][x].sum(key); } return ret; }; // the path from u to root auto hldAdd = [&](int u, int key, int val) { // cerr<<"hldAdd "<<u<<" "<<key<<" "<<val<<endl; for (; u != -1; ) { const int h = head[u]; // add to [0, ord[u] - ord[h]] // cerr<<" "<<h<<" "<<(lens[h] - (ord[u] - ord[h]) - 1)<<endl; bAdd(h, lens[h] - (ord[u] - ord[h]) - 1, key, val); u = par[h]; } }; auto hldSum = [&](int u, int key) { // cerr<<"hldSum "<<u<<" "<<key<<endl; const int h = head[u]; // sum at (ord[u] - ord[h]) // cerr<<" "<<h<<" "<<(lens[h] - (ord[u] - ord[h]))<<endl; const int ret = bSum(h, lens[h] - (ord[u] - ord[h]), key); return ret; }; vector<vector<int>> pp(E, vector<int>(N)); vector<vector<Int>> dd(E, vector<Int>(N)); pp[0] = par; for (int u = 0; u < N - 1; ++u) { dd[0][u] = (par[u] == -1) ? 0 : (dist[u] - dist[par[u]]); } for (int e = 0; e < E - 1; ++e) { for (int u = 0; u < N; ++u) { if (pp[e][u] == -1) { pp[e + 1][u] = -1; dd[e + 1][u] = dd[e][u]; } else { pp[e + 1][u] = pp[e][pp[e][u]]; dd[e + 1][u] = dd[e][u] + dd[e][pp[e][u]]; } } } /* vector<int>brt(Q,-58); if(N<=2000&&Q<=2000){ vector<vector<Int>>wss(N); for(int q=0;q<Q;++q){ if(TYP[q]==0){ for(int u=V[q];u!=-1&&dist[V[q]]-dist[u]<=L[q];u=par[u]){ // cerr<<"brt add "<<u<<" "<<T[q]+dist[V[q]]<<endl; wss[u].push_back(T[q]+dist[V[q]]); } }else{ sort(wss[V[q]].begin(),wss[V[q]].end()); brt[q]=upper_bound(wss[V[q]].begin(),wss[V[q]].end(),T[q]+dist[V[q]])-wss[V[q]].begin(); // printf("%d\n",brt[q]); } } // continue; } // exit(1); //*/ vector<int> ans(Q, -58); vector<pair<pair<Int, int>, int>> qrys(Q); for (int q = 0; q < Q; ++q) { qrys[q] = make_pair(make_pair(T[q] + dist[V[q]], TYP[q]), q); } sort(qrys.begin(), qrys.end()); for (const auto &qry : qrys) { const int q = qry.second; switch (TYP[q]) { case 0: { Int l = L[q]; assert(0<=l); assert(l<=1'000'000'000'000LL); int u = V[q]; for (int e = E; e--; ) { if (pp[e][u] != -1 && l - dd[e][u] >= 0) { l -= dd[e][u]; u = pp[e][u]; } } // cerr<<"q = "<<q<<": u = "<<u<<endl; assert(dist[V[q]]-dist[u]<=L[q]); // if(par[u]!=-1)assert(dist[V[q]]-dist[par[u]]>L[q]); hldAdd(V[q], q, +1); hldAdd(par[u], q, -1); } break; case 1: { // cerr<<"q = "<<q<<endl; ans[q] = hldSum(V[q], q); } break; default: assert(false); } } for (int q = 0; q < Q; ++q) { if (TYP[q] == 1) { printf("%d\n", ans[q]); } } /* if(N<=2000&&Q<=2000){ for(int q=0;q<Q;++q)if(brt[q]!=ans[q]){ cerr<<"q = "<<q<<": "<<brt[q]<<" "<<ans[q]<<endl; assert(false); } } //*/ } return 0; }