#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; struct HeavyLightDecomposition{ vector>> g; vector in, out, rev, cnt, head, par; vector d, din; HeavyLightDecomposition(const vector>> &g):g(g), in(g.size()), out(g.size()), rev(g.size()), cnt(g.size()), head(g.size()), par(g.size()), d(g.size()), din(g.size()){} void dfs(int x, int p){ cnt[x]=1, par[x]=p; int mx=-1, k=-1; for(int i=0; i0) swap(g[x][k], g[x][0]); } void dfs2(int x, int p, int &t){ in[x]=t++; rev[in[x]]=x; for(int i=0; i void query(int u, int v, const Q &q){ //T ret=e; for(; ; v=par[head[v]]){ if(in[u]>in[v]) swap(u, v); if(head[u]==head[v]) break; q(in[head[v]], in[v]+1); //ret=f(q(in[head[v]], in[v]+1), ret); } q(in[u], in[v]+1); //ret=f(q(in[u], in[v]+1), ret); //return ret; } }; template struct BIT{ vector bit; int size; BIT(){} BIT(int n):size(n), bit(n+1, 0){} void init(int n){ size=n; bit.resize(n+1, 0); } T sum(int i){ //[0, i) T s=0; while(i>0){ s+=bit[i]; i-=(i&(-i)); } return s; } T sum(int l, int r){ //[l, r) return sum(r)-sum(l); } void add(int i, T x){ i++; while(i<=size){ bit[i]+=x; i+=(i&(-i)); } } }; int main() { int n, q; cin>>n>>q; vector>> g(n); for(int i=0; i>a>>b>>c; a--; b--; g[a].push_back({b, c}); g[b].push_back({a, c}); } HeavyLightDecomposition hld(g); hld.build(); int type[100010], v[100010], h[100010]; ll t[100010], l[100010]; int sz=1; while(sz> seg(2*sz); auto add0=[&](int l, int r, ll x){ l+=sz, r+=sz; for(;l>=1, r>>=1){ if(r&1) seg[--r].push_back(x); if(l&1) seg[l++].push_back(x); } }; for(int i=0; i>type[i]>>v[i]>>t[i]>>l[i]; v[i]--; if(type[i]==0){ h[i]=hld.la(v[i], l[i]); auto qr0=[&](int l, int r){ add0(l, r, hld.d[v[i]]+t[i]); }; hld.query(h[i], v[i], qr0); } } vector> bit(2*sz); for(int i=1; i<2*sz; i++){ sort(seg[i].begin(), seg[i].end()); seg[i].erase(unique(seg[i].begin(), seg[i].end()), seg[i].end()); bit[i].init((int)seg[i].size()); } auto add=[&](int l, int r, ll x){ l+=sz, r+=sz; for(;l>=1, r>>=1){ if(r&1){ r--; int p=lower_bound(seg[r].begin(), seg[r].end(), x)-seg[r].begin(); bit[r].add(p, 1); } if(l&1){ int p=lower_bound(seg[l].begin(), seg[l].end(), x)-seg[l].begin(); bit[l].add(p, 1); l++; } } }; for(int i=0; i1){ p>>=1; q=upper_bound(seg[p].begin(), seg[p].end(), x)-seg[p].begin(); ans+=bit[p].sum(q); } printf("%d\n", ans); } } return 0; }