#include #include #include #include #include #include #include #include #include #include #define mkp make_pair #define mkt make_tuple #define rep(i,n) for(int i = 0; i < (n); ++i) #define all(v) v.begin(),v.end() using namespace std; typedef long long ll; const ll MOD=1e9+7; template void chmin(T &a,const T &b){if(a>b) a=b;} template void chmax(T &a,const T &b){if(a bit; BIT(){} BIT(int size){ bit.resize(size,0); } void initialize(int size){ bit.resize(size,0); } ll sum(int i){ ll s=0; while(i>0){ s+=bit[i]; i-=i&(-i); } return s; } void add(int i,ll x){//i!=0 while(i> g; vector in,out,head,par,dep,sz; int times; int root; vector rev; vector dist; vector disrev; HeavyLightDecomposition(int V,vector> &G,int root=0): g(G),in(V),out(V),head(V),par(V),dep(V),sz(V),root(root),dist(V),rev(V),disrev(V){ times=0; sz_dfs(root,-1); hld_dfs(root,-1); for(int i=0;isz[g[now][0].to]) swap(e,g[now][0]); } } void hld_dfs(int now,int p){ in[now]=times++; rev[in[now]]=now; for(auto e:g[now]){ if(e.to==p) continue; head[e.to]=(e.to == g[now][0].to ? head[now] : e.to); hld_dfs(e.to,now); } out[now]=times; } int lca(int u,int v){ for(;;v=par[head[v]]){ if(in[u]>in[v]) swap(u,v); if(head[u]==head[v]) return u; } } int distance(int u,int v){ return dep[u]+dep[v]-2*dep[lca(u,v)]; } int climb(int v,ll lim){ for(;;v=par[head[v]]){ int u=head[v]; if(u==0||dist[par[u]]+lim void update(int v,const T &x,const G &g){//辺の時は0を使わない(INFのまま) //g(in[v]+1,out[v],x);//部分木(辺) //g(in[v],out[v],x);//部分木(頂点) //g(in[v],in[v]+1,x);//一点 } /*ex) ll ans=0; hld.query(u,v,[&](int a,int b){ ans+=seg.getSum(a,b); },true); */ template void query(int u,int v,ll x,const F &f,bool isedge){ for(;;v=par[head[v]]){ if(in[u]>in[v]) swap(u,v); if(head[u]==head[v]) break; f(in[head[v]],in[v]+1,x); } if(isedge&&u==v) return; f(in[u]+isedge,in[v]+1,x); } }; int main(){ cin.tie(0); ios::sync_with_stdio(false); int N,Q; cin>>N>>Q; vector> g(N); rep(i,N-1){ int a,b; ll c; cin>>a>>b>>c; a--;b--; g[a].push_back({b,c}); g[b].push_back({a,c}); } vector type(Q),V(Q); vector T(Q),L(Q); rep(i,Q) cin>>type[i]>>V[i]>>T[i]>>L[i]; rep(i,Q) V[i]--; HeavyLightDecomposition hld(N,g); int sz=1; while(sz> segment(2*sz); auto preadd = [&](int l,int r,ll x){ l+=sz;r+=sz; while(l>=1;r>>=1; } }; vector up(Q,-1); for(int q=0;q bit(2*sz); for(int i=0;i<2*sz;i++){ sort(all(segment[i])); segment[i].erase(unique(all(segment[i])),segment[i].end()); bit[i].initialize(segment[i].size()+1); } auto add = [&](int l,int r,ll x){ l+=sz;r+=sz; while(l>=1;r>>=1; } }; for(int q=0;q=1){ int z=upper_bound(all(segment[now]),target)-segment[now].begin(); ans+=bit[now].sum(z); now>>=1; } cout<