#include #define rep(i,n)for(int i=0;i<(n);i++) using namespace std; typedef long long ll; typedef pairP; struct BIT2D{ vector>bit; BIT2D(){} BIT2D(int n,int m){ bit=vector>(n+10,vector(m+10)); } void add(int a,int b,int val){ for(int x=a+1;xE[60000]; ll d[60000]; //深さ int vid[60000],rev[60000]; //Euler Tour上の頂点の順番 int cl[60000],cr[60000]; //部分木に対応する区間 int node_cnt; void dfs(int v,int p){ cl[v]=node_cnt; vid[v]=node_cnt++; rev[vid[v]]=v; for(auto u:E[v]){ if(u.second==p)continue; d[u.second]=d[v]+u.first; dfs(u.second,v); } cr[v]=node_cnt; } int ty[200000],v[200000]; ll t[200000],l[200000]; struct st{ ll v; //頂点のid P p; //(出発時間、持続時間) int id; //何番目に追加される? int X,Y; //bucketで使う情報 }vs[200000]; //全灯籠の列 (Euler Tour順序でソート) int pos[200000]; const int B=1024; struct Bucket{ BIT2D bit; vectorxs,ys; vectoridx; void pre_add(st&s){ ll X=s.p.first+d[s.v],Y=d[s.v]-s.p.second; xs.push_back(X); ys.push_back(Y); idx.push_back(pos[s.id]); } void init(){ sort(xs.begin(),xs.end());xs.erase(unique(xs.begin(),xs.end()),xs.end()); sort(ys.begin(),ys.end());ys.erase(unique(ys.begin(),ys.end()),ys.end()); for(int i:idx){ vs[i].X=lower_bound(xs.begin(),xs.end(),vs[i].p.first+d[vs[i].v])-xs.begin(); vs[i].Y=lower_bound(ys.begin(),ys.end(),d[vs[i].v]-vs[i].p.second)-ys.begin(); } bit=BIT2D(xs.size(),ys.size()); } void add(int id){ bit.add(vs[id].X,vs[id].Y,1); } int query(ll x,ll y){ x=upper_bound(xs.begin(),xs.end(),x)-xs.begin(); y=upper_bound(ys.begin(),ys.end(),y)-ys.begin(); return bit.sum(x-1,y-1); } }bucket[100000]; int main(){ int n,q;cin>>n>>q; assert(1<=n&&n<=50000); assert(1<=q&&q<=100000); rep(i,n-1){ int a,b;ll c;scanf("%d%d%lld",&a,&b,&c);a--;b--; E[a].push_back(P(c,b)); E[b].push_back(P(c,a)); } dfs(0,-1); int vcnt=0; rep(i,q){ scanf("%d%d%lld%lld",&ty[i],&v[i],&t[i],&l[i]);v[i]--; if(ty[i]==0)vs[vcnt++]={v[i],P(t[i],l[i]),i}; } sort(vs,vs+vcnt,[&](st a,st b){return vid[a.v]>10; for(int j=i;j1){ int t=(ok1+ng1)/2; if(vid[vs[t].v]>=cl[i])ok1=t; else ng1=t; } int ok2=vcnt,ng2=-1; while(ok2-ng2>1){ int t=(ok2+ng2)/2; if(vid[vs[t].v]>=cr[i])ok2=t; else ng2=t; } cl[i]=ok1; cr[i]=ok2; } rep(i,q){ if(ty[i]==0){ bucket[pos[i]>>10].add(pos[i]); } else{ int L=cl[v[i]],R=cr[v[i]]; int ans=0; ll X=d[v[i]]+t[i],Y=d[v[i]]; while(L>10].query(X,Y); } printf("%d\n",ans); } } }