#define PROBLEM "https://yukicoder.me/problems/4852" #include using namespace std; #define call_from_test #ifndef call_from_test #include using namespace std; #endif /* * @docs docs/binaryindexedtree.md */ //BEGIN CUT HERE template struct BIT{ int n; vector bit; // 1-indexed BIT(int n_):n(n_+1),bit(n+1,0){} T sum(int i){ T s(0); for(int x=i;x>0;x-=(x&-x)) s+=bit[x]; return s; } void add(int i,T a){ if(i==0) return; for(int x=i;x<=n;x+=(x&-x)) bit[x]+=a; } // [l, r) T query(int l,int r){ return sum(r-1)-sum(l-1); } int lower_bound(int w){ if(w<=0) return 0; int x=0,r=1; while(r0;k>>=1){ if(x+k<=n&&bit[x+k] using namespace std; #endif //BEGIN CUT HERE 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; } //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 class EulerTourForVertex{ private: vector 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]); } }; //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #ifndef call_from_test #include using namespace std; #endif //BEGIN CUT HERE 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; } }; //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #ifndef call_from_test #include using namespace std; #define call_from_test #include "eulertourforvertex.cpp" #include "lowestcommonancestor.cpp" #undef call_from_test #endif /** * @see https://smijake3.hatenablog.com/entry/2019/09/15/200200 */ //BEGIN CUT HERE 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(); } }; //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 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())); } //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #undef call_from_test #ifdef SANITIZE #define IGNORE #endif signed main(){ cin.tie(0); ios::sync_with_stdio(0); const char newl = '\n'; using ll = long long; using P = pair; int n,q; cin>>n>>q; vector> G(n+1); AuxiliaryTree H(n+1); for(int i=1;i>a>>b>>c; G[a].emplace_back(b,c); G[b].emplace_back(a,c); H.add_edge(a,b); } // add 0 for root H.add_edge(0,1); H.build(0); const ll INF = 1e15; G[0].emplace_back(1,INF); vector dep(n+1); 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); // vanish vertices vector rs(q); for(int i=0;i=0;k--){ int p=H.lca.par[k][r]; if(~p and d<=dep[p]) r=p; } rs[i]=H.lca.par[0][r]; } vector pos; for(int i=0;i bit(pos.size()); vector cs(q); for(int i=0;i que; que.emplace(0,q); vector ans(q); vector> add(n+1),sub(n+1),query(n+1); while(!que.empty()){ auto [L,R]=que.front();que.pop(); if(L+1==R) continue; int M=(L+R)>>1; vector ss; for(int i=L;ivoid{ for(int i:query[v]) ans[i]-=bit.sum0(cs[i]); for(int u:H.T[v]) if(u!=p) dfs(u,v); expand(v); for(int i:query[v]) ans[i]+=bit.sum0(cs[i]); })(0,-1); H.clear(ss); for(int i=M;i