#include using namespace std; using Int = long long; const char newl = '\n'; template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a void drop(const T &x){cout< vector read(size_t n){ vector ts(n); for(size_t i=0;i>ts[i]; return ts; } struct Sack{ using F = function; int n; vector sz,hvy,big; vector > G,Q; F expand,shrink,query,reset; Sack(int n,F expand,F shrink,F query,F reset): sz(n,1),hvy(n,-1),big(n,0),G(n),Q(n), expand(expand),shrink(shrink), query(query),reset(reset){} void add_edge(int u,int v){ G[u].emplace_back(v); G[v].emplace_back(u); } void add_query(int v,int k){ Q[v].emplace_back(k); sz[v]++; } void add(int v,int p,int x){ if(x==1) expand(v); else shrink(v); for(int u:G[v]) if(u!=p&&!big[u]) add(u,v,x); } void dfs(int v=0,int p=-1,bool k=0){ for(int u:G[v]) if(u!=p&&u!=hvy[v]) dfs(u,v,0); if(~hvy[v]){ dfs(hvy[v],v,1); big[hvy[v]]=1; } add(v,p,1); for(int k:Q[v]) query(k); if(~hvy[v]) big[hvy[v]]=0; if(!k) add(v,p,0),reset(v); } void build(int v=0,int p=-1){ for(int u:G[v]){ if(u==p) continue; build(u,v); if(hvy[v]<0||sz[hvy[v]] ls,rs; int pos; void dfs(int v,int p){ ls[v]=pos++; for(int u:G[v]) if(u!=p) dfs(u,v); rs[v]=pos; } public: vector< vector > G; EulerTourForVertex(){} EulerTourForVertex(int n):ls(n),rs(n),G(n){} void add_edge(int u,int v){ G[u].emplace_back(v); G[v].emplace_back(u); } void build(int r=0){ pos=0; dfs(r,-1); } int idx(int v){return ls[v];} template void exec(int v,F f){ f(ls[v],rs[v]); } }; struct LowestCommonAncestor{ int n,h; vector< vector > G,par; vector dep; LowestCommonAncestor(){} LowestCommonAncestor(int n):n(n),G(n),dep(n){ h=1; while((1<(n,-1)); } void add_edge(int u,int v){ G[u].emplace_back(v); G[v].emplace_back(u); } void dfs(int v,int p,int d){ par[0][v]=p; dep[v]=d; for(int u:G[v]) if(u!=p) dfs(u,v,d+1); } void build(int r=0){ dfs(r,-1,0); for(int k=0;k+1dep[v]) swap(u,v); for(int k=0;k>k&1) v=par[k][v]; if(u==v) return u; for(int k=h-1;k>=0;k--) if(par[k][u]!=par[k][v]) u=par[k][u],v=par[k][v]; return par[0][u]; } int distance(int u,int v){ return dep[u]+dep[v]-dep[lca(u,v)]*2; } }; struct AuxiliaryTree : EulerTourForVertex{ using super = EulerTourForVertex; LowestCommonAncestor lca; vector> T; AuxiliaryTree(){} AuxiliaryTree(int n):super(n),lca(n),T(n){} void build(int r=0){ super::build(r); lca.G=super::G; lca.build(r); } void add_aux_edge(int u,int v){ T[u].emplace_back(v); T[v].emplace_back(u); } using super::idx; void query(vector &vs){ assert(!vs.empty()); sort(vs.begin(),vs.end(), [&](int a,int b){return idx(a) st; st.emplace(vs[0]); for(int i=0;i+11){ int c=st.top();st.pop(); add_aux_edge(st.top(),c); } } void clear(const vector &ws){ for(int w:ws) T[w].clear(); } }; template struct RangeCount{ struct BIT{ vector dat; BIT(){} BIT(int n){dat.assign(++n,0);} T sum(int k){ T res=0; for(;k;k-=k&-k) res+=dat[k]; return res; } void add(int k,T v){ for(++k;k<(int)dat.size();k+=k&-k) dat[k]+=v; } }; int n; using ll = long long; vector< vector > val; vector dat; RangeCount(){} RangeCount(int n_){ n=1; while(n()); dat.reserve(n<<1); } void preupdate(int a,ll x){ a+=n; while(a){ val[a].emplace_back(x); a>>=1; } } void build(){ for(int i=0;i>=1; } } T calc(int k,ll x,ll y){ auto &v=val[k]; int p=lower_bound(v.begin(),v.end(),x)-v.begin(); int q=lower_bound(v.begin(),v.end(),y)-v.begin(); return dat[k].sum(q)-dat[k].sum(p); } // [a, b) * [x, y) T query(int a,int b,ll x,ll y){ T res=0; for(int l=a+n,r=b+n;l>=1,r>>=1){ if(l&1) res+=calc(l++,x,y); if(r&1) res+=calc(--r,x,y); } return res; } }; template void read_tuple_impl(TV&) {} template void read_tuple_impl(TV& ts) { get(ts).emplace_back(*(istream_iterator(cin))); read_tuple_impl(ts); } template decltype(auto) read_tuple(size_t n) { tuple...> ts; for(size_t i=0;i(ts); return ts; } 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 V compress(V vs){ sort(vs.begin(),vs.end()); vs.erase(unique(vs.begin(),vs.end()),vs.end()); return vs; } template map dict(const vector &vs){ map res; for(int i=0;i<(int)vs.size();i++) res[vs[i]]=i; return res; } map dict(const string &s){ return dict(vector(s.begin(),s.end())); } using i16 = int16_t; using i32 = int32_t; using i64 = int64_t; using u16 = uint16_t; using u32 = uint32_t; using u64 = uint64_t; // AtCoder const i64 CYCLES_PER_SEC = 2800000000; struct Timer { i64 start; Timer(){reset();} void reset(){start=getCycle();} inline double get(){return (double)(getCycle()-start)/CYCLES_PER_SEC;} inline i64 getCycle(){ u32 low,high; __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high)); return ((i64)low)|((i64)high<<32); } }; Timer timer; //INSERT ABOVE HERE signed main(){ cin.tie(0); ios::sync_with_stdio(0); using ll = long long; int n,q; cin>>n>>q; using P = pair; vector> G(n); AuxiliaryTree H(n); for(int i=1;i>a>>b>>c; a--;b--; G[a].emplace_back(b,c); G[b].emplace_back(a,c); H.add_edge(a,b); } H.build(0); vector dep(n); MFP([&](auto dfs,int v,int p,ll d)->void{ dep[v]=d; for(auto [u,c]:G[v]) if(u!=p) dfs(u,v,d+c); })(0,-1,0); auto [type,vs,ts,ls]=read_tuple(q); for(int &v:vs) v--; vector ans(q); queue

que; que.emplace(0,q); while(!que.empty()){ if(timer.get()>4.0) break; auto [L,R]=que.front();que.pop(); if(L+1==R) continue; int M=(L+R)>>1; vector ss; for(int i=L;i> B(m); for(int i=L;i pos; for(int i=L;i seg(pos.size()); for(int i=L;i