// verification-helper: PROBLEM https://yukicoder.me/problems/3912 #include using namespace std; #define call_from_test struct Centroid{ inline static mt19937 mt; vector dead; vector< vector > G; Centroid(int n):dead(n,0),G(n){} void add_edge(int u,int v){ G[u].emplace_back(v); G[v].emplace_back(u); } void dfs(int v,int p,vector& cs){ for(int u:G[v]){ if(dead[u]) continue; cs.emplace_back(v); if(u!=p) dfs(u,v,cs); } if(cs.empty()) cs.emplace_back(v); } vector build(int r) { vector cs; dfs(r,-1,cs); shuffle(cs.begin(),cs.end(),mt); cs.resize(1); return cs; } const vector& operator[](int k)const{return G[k];} void disable(int v){dead[v]=1;} void enable(int v){dead[v]=0;} int alive(int v){return !dead[v];} }; template struct FixPoint : F{ FixPoint(F&& f):F(forward(f)){} template decltype(auto) operator()(Args&&... args) const{ return F::operator()(*this,forward(args)...); } }; template inline decltype(auto) MFP(F&& f){ return FixPoint{forward(f)}; } template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a struct SegmentTree{ using H = function; int n,height; H h; E ei; vector laz; SegmentTree(H h,E ei):h(h),ei(ei){} void init(int n_){ n=1;height=0; while(n>i); } void update(int a,int b,E x){ if(a>=b) return; thrust(a+=n); thrust(b+=n-1); for(int l=a,r=b+1;l>=1,r>>=1){ if(l&1) laz[l]=h(laz[l],x),l++; if(r&1) --r,laz[r]=h(laz[r],x); } } E get_val(int a){ thrust(a+=n); return laz[a]; } void set_val(int a,E x){ thrust(a+=n); laz[a]=x; } }; #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n,q; cin>>n>>q; Centroid G(n); for(int i=1;i>a>>b; a--;b--; G.add_edge(a,b); } vector xs(q),ys(q),zs(q); for(int i=0;i>xs[i]>>ys[i]>>zs[i]; vector> H(n); for(int i=0;i dep(n); using ll = long long; vector ans(q,0); auto h=[&](ll a,ll b){return a+b;}; SegmentTree seg(h,0); seg.init(n*2); queue que; que.emplace(G.build(0)[0]); while(!que.empty()){ int r=que.front();que.pop(); dep[r]=0; // add for all { int len=1; vector qs(H[r]); for(int t:G[r]){ if(!G.alive(t)) continue; MFP([&](auto dfs,int v,int p,int d)->void{ dep[v]=d; chmax(len,d+1); for(int i:H[v]) qs.emplace_back(i); for(int u:G[v]){ if(u==p) continue; if(!G.alive(u)) continue; dfs(u,v,d+1); } })(t,r,1); } seg.init(len); sort(qs.begin(),qs.end()); for(int i:qs){ ans[i]+=seg.get_val(dep[xs[i]]); if(ys[i]>=dep[xs[i]]) seg.update(0,min(len,ys[i]-dep[xs[i]]+1),zs[i]); } } // sub for subtree { for(int t:G[r]){ if(!G.alive(t)) continue; int len=1; vector qs; MFP([&](auto dfs,int v,int p,int d)->void{ dep[v]=d; chmax(len,d+1); for(int i:H[v]) qs.emplace_back(i); for(int u:G[v]){ if(u==p) continue; if(!G.alive(u)) continue; dfs(u,v,d+1); } })(t,r,1); seg.init(len); sort(qs.begin(),qs.end()); for(int i:qs){ ans[i]-=seg.get_val(dep[xs[i]]); if(ys[i]>=dep[xs[i]]) seg.update(0,min(len,ys[i]-dep[xs[i]]+1),zs[i]); } } } G.disable(r); for(int t:G[r]) if(G.alive(t)) que.emplace(G.build(t)[0]); } for(auto a:ans) cout<