#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 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]] c(n); for(int i=0;i cnt(n+1,0); vector ans(n,0); int mx=0; ll res=0; auto expand= [&](int v){ cnt[c[v]]++; if(mx c(n),dep(n); vector vs(q),hs(q),ans(q); vector cnt(n+1,0),odd(n+1,0); auto flip= [&](int v){ odd[dep[v]]-=(cnt[dep[v]]>>c[v])&1; cnt[dep[v]]^=(1<>c[v])&1; }; auto query =[&](int k){ans[k]=odd[hs[k]]<=1;}; auto reset =[&](int v){(void)v;}; Sack sc(n,flip,flip,query,reset); for(int i=1;i dfs= [&](int v,int p,int d){ dep[v]=d; for(int u:G[v]){ if(u==p) continue; dfs(u,v,d+1); } }; dfs(0,-1,1); } char* buf = new char[500500]; scanf("%s",buf); for(int i=0;i dep(n),rs; vector vs,hs,ans; vector cnt(n+1,0); auto expand=[&](int v){cnt[dep[v]]++;}; auto shrink=[&](int v){cnt[dep[v]]--;}; auto query =[&](int k){ans[k]=cnt[dep[vs[k]]+hs[k]]-1;}; auto reset =[&](int v){(void)v;}; Sack sc(n,expand,shrink,query,reset); for(int i=0;i > ps(20,vector(n,-1)); { auto &G=sc.G; function dfs= [&](int v,int p,int d){ ps[0][v]=p; dep[v]=d; for(int u:G[v]){ if(u==p) continue; dfs(u,v,d+1); } }; for(int r:rs) dfs(r,-1,1); } int q; scanf("%d",&q); vs.assign(q,0); hs.assign(q,0); ans.assign(q,0); for(int k=0;k+1<20;k++) for(int i=0;i>i)&1) v=ps[i][v]; return v; }; for(int i=0;i 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 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 rev(n+1); queue

que; que.emplace(0,q); vector ans(q); 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;i> add(m),sub(m); for(int i=L;i