#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using Int = long long; template ostream &operator<<(ostream &os, const pair &a) { return os << "(" << a.first << ", " << a.second << ")"; }; template void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; } template bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; } template bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; } int N, Q; vector A, B; vector C; vector TYP, V; vector T, L; vector> G; vector par, sz, dep; vector dist; int O; vector 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 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 lens(N, 0); for (int u = 0; u < N; ++u) { ++lens[head[u]]; } BIT_N = Q; vector> 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 "<= 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 "<> pp(E, vector(N)); vector> dd(E, vector(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]]; } } } /* vectorbrt(Q,-58); if(N<=2000&&Q<=2000){ vector>wss(N); for(int q=0;q ans(Q, -58); vector, 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]; 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 = "<