#define PROBLEM "https://yukicoder.me/problems/3912" #include using namespace std; #define call_from_test #ifndef call_from_test #include using namespace std; #endif //BEGIN CUT HERE struct Centroid{ vector sz,dead; vector< vector > G; Centroid(){} Centroid(int n):sz(n,1),dead(n,0),G(n){} void add_edge(int u,int v){ G[u].emplace_back(v); G[v].emplace_back(u); } int dfs(int v,int p){ sz[v]=1; for(int u:G[v]) if(u!=p&&!dead[u]) sz[v]+=dfs(u,v); return sz[v]; } void find(int v,int p,int tmp,vector &cs) { int ok=1; for (int u:G[v]){ if(u==p||dead[u]) continue; find(u,v,tmp,cs); ok&=(sz[u]<=tmp/2); } ok&=(tmp-sz[v]<=tmp/2); if(ok) cs.emplace_back(v); } vector build(int r) { int tmp=dfs(r,-1); vector cs; find(r,-1,tmp,cs); 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];} }; //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #ifndef call_from_test #include using namespace std; #endif //BEGIN CUT HERE 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)}; } //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #ifndef call_from_test #include using namespace std; #endif //BEGIN CUT HERE template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a using namespace std; #endif //BEGIN CUT HERE template 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; } }; //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #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.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.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.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.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.G[r]) if(G.alive(t)) que.emplace(G.build(t)[0]); } for(auto a:ans) cout<