#include #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; typedef long long ll; typedef vector vi; typedef pair pii; #define MP make_pair #define PB push_back #define inf 1000000007 #define rep(i,n) for(int i = 0; i < (int)(n); ++i) #define all(x) (x).begin(),(x).end() template void Fill(A (&array)[N], const T &val){ std::fill( (T*)array, (T*)(array+N), val ); } template inline bool chmax(T &a, T b){ if(a inline bool chmin(T &a, T b){ if(a>b){ a = b; return true; } return false; } template class segtree { private: int n,sz; vector node; public: void init(const vector& v){ sz = (int)v.size(); n = 1; while(n < sz){ n *= 2; } node.assign(2*n,0); for(int i = 0; i < sz; i++){ node[i+n] = v[i]; } for(int i=n-1; i>=1; i--){ node[i] =node[2*i] + node[2*i+1]; } } void update(int k,T a){ node[k+=n] += a; while(k>>=1){ node[k] = node[2*k]+node[2*k+1]; } } T query(int a,int b){ T res1 = 0; T res2 = 0; a += n, b += n; while(a != b){ if(a & 1) res1 = res1+node[a++]; if(b & 1) res2 = node[--b]+ res2; a >>= 1, b>>= 1; } return res1+res2; } void print(){ for(int i = 0; i < sz; i++){ cout << query(i,i+1) << " "; } cout << endl; } }; //座標の型, 値の型 template class RangeTree { public: static_assert(std::is_integral::value, "Integral required."); private: using CT = CandidateType; using VT = ValueType; using pcc = pair; using pci = pair; int n, sz; vector > seg; // y座標, x座標 vector > yx; // y座標, x座標 vector sorted; void update_(int id, const CT x, const CT y, const VT val) { id += n-1; const int yid = lower_bound(all(yx[id]), pcc(y, x)) - yx[id].begin(); seg[id].update(yid, val); while(id > 0){ id = (id - 1) / 2; const int yid = lower_bound(all(yx[id]), pcc(y, x)) - yx[id].begin(); seg[id].update(yid, val); } } VT query(const int lxid, const int rxid, const CT ly, const CT ry, const int k, const int l, const int r) { if(r <= lxid || rxid <= l) return 0; if(lxid <= l && r <= rxid){ const int lyid = lower_bound(all(yx[k]), pcc(ly, numeric_limits::min())) - yx[k].begin(); const int ryid = upper_bound(all(yx[k]), pcc(ry, numeric_limits::min())) - yx[k].begin(); return (lyid >= ryid) ? 0 : seg[k].query(lyid, ryid); }else{ return query(lxid, rxid, ly, ry, 2*k+1, l, (l+r)/2) + query(lxid, rxid, ly, ry, 2*k+2, (l+r)/2, r); } } public: // 座標, 点の値 RangeTree(const vector& cand, const vector& val) : n(1), sz((int)cand.size()), sorted(sz){ while(n < sz) n *= 2; for(int i = 0; i < sz; ++i){ sorted[i] = {cand[i].first, i}; } sort(all(sorted), [&](const pcc& a, const pcc& b){ return (a.first == b.first) ? (cand[a.second].second < cand[b.second].second) : (a.first < b.first); }); yx.resize(2*n-1), seg.resize(2*n-1); for(int i = 0; i < sz; ++i){ yx[i+n-1] = {{sorted[i].second, sorted[i].first}}; vector arg = {val[sorted[i].second]}; seg[i+n-1].init(arg); sorted[i].second = cand[sorted[i].second].second; } for(int i = n-2; i >= 0; --i){ yx[i].resize((int)yx[2*i+1].size() + (int)yx[2*i+2].size()); if(yx[i].empty()) continue; merge(all(yx[2*i+1]), all(yx[2*i+2]), yx[i].begin(), [&](const pcc& a, const pcc& b){ return (cand[a.first].second == cand[b.first].second) ? (a.second < b.second) : (cand[a.first].second < cand[b.first].second); }); vector arg((int)yx[i].size()); for(int j = 0; j < (int)yx[i].size(); ++j){ arg[j] = val[yx[i][j].first]; } seg[i].init(arg); } for(int i = 0; i < 2*n-1; ++i){ for(pcc& e : yx[i]){ e.first = cand[e.first].second; } } } // 点 (x,y) の更新を行う void update(const CT x, const CT y, const VT val){ const int id = lower_bound(all(sorted), pcc(x, y)) - sorted.begin(); return update_(id, x, y, val); } // [lx,rx) × [ly,ry) の長方形領域のクエリに答える VT query(const CT lx, const CT ly, const CT rx, const CT ry){ const int lxid = lower_bound(all(sorted), pcc(lx, numeric_limits::min())) - sorted.begin(); const int rxid = upper_bound(all(sorted), pcc(rx, numeric_limits::min())) - sorted.begin(); return (lxid >= rxid) ? 0 : query(lxid, rxid, ly, ry, 0, 0, n); } }; vector > > g; ll parent[17][50000]; ll dep[50000]; int in[50000]; int out[50000]; int te; void init(int id,int pre){ in[id] = te; te++; for(auto x:g[id]){ if(x.first == pre)continue; dep[x.first] = dep[id] + x.second; parent[0][x.first] = id; init(x.first,id); } out[id] = te; te++; } int main(){ cin.tie(0); ios::sync_with_stdio(false); int n,Q; cin >> n >> Q; g.resize(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}); } init(0,-1); // rep(i,n){ // cerr << in[i] << " " << out[i] << endl; // } vector,int> > p; vector > cand; cand.push_back({0,0}); rep(tt,Q){ int type,V; ll T,L; cin >> type >> V >> T >> L; V--; if(type==0){ p.push_back({{T+dep[V],in[V]},1});cand.push_back({T+dep[V],in[V]}); ll TT = T+dep[V]; for(int i=16;i>=0;i--){ int P = parent[i][V]; if(dep[V]-dep[P] <= L){ L -= dep[V]-dep[P]; V = P; break; } } if(V!=0){ p.push_back({{TT,in[parent[0][V]]},-1}); cand.push_back({TT,in[parent[0][V]]}); } }else{ p.push_back({{T+dep[V],V},0}); cand.push_back({T+dep[V],in[V]}); cand.push_back({T+dep[V],out[V]}); } } sort(all(cand)); cand.erase(unique(all(cand)),cand.end()); vector ppp((int)cand.size()); RangeTree RT(cand,ppp); for(auto&x:p){ if(x.second!=0){ RT.update(x.first.first,x.first.second,x.second); // cerr << x.first.first << " " << x.first.second << " " << x.second << endl; }else{ // cerr << x.first.second << endl; // cerr << "Q:" << 0 << " " << in[x.first.second] << " " << x.first.first+1 << " " << out[x.first.second] + 1 << endl; cout << RT.query(0,in[x.first.second],x.first.first+1,out[x.first.second]+1) << "\n"; } } return 0; }