#include using namespace std; using ll=long long; using ull=unsigned long long; using P=pair; templateusing minque=priority_queue,greater>; templatebool chmax(T &a,const T &b){return (abool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} templateistream &operator>>(istream &is,pair&p){is>>p.first>>p.second;return is;} templateistream &operator>>(istream &is,tuple&a){is>>std::get<0>(a)>>std::get<1>(a)>>std::get<2>(a);return is;} templateistream &operator>>(istream &is,array&a){for(auto&i:a)is>>i;return is;} templateistream &operator>>(istream &is,vector &a){for(auto &i:a)is>>i;return is;} templatevoid operator++(pair&a,int n){a.first++,a.second++;} templatevoid operator--(pair&a,int n){a.first--,a.second--;} templatevoid operator++(vector&a,int n){for(auto &i:a)i++;} templatevoid operator--(vector&a,int n){for(auto &i:a)i--;} #define overload3(_1,_2,_3,name,...) name #define rep1(i,n) for(int i=0;i<(int)(n);i++) #define rep2(i,l,r) for(int i=(int)(l);i<(int)(r);i++) #define rep(...) overload3(__VA_ARGS__,rep2,rep1)(__VA_ARGS__) #define reps(i,l,r) rep2(i,l,r) #define all(x) x.begin(),x.end() #define pcnt(x) __builtin_popcountll(x) #define fin(x) return cout<<(x)<<'\n',static_cast(0) #define yn(x) cout<<((x)?"Yes\n":"No\n") #define uniq(x) sort(all(x)),x.erase(unique(all(x)),x.end()) template inline int fkey(vector&z,T key){return lower_bound(z.begin(),z.end(),key)-z.begin();} ll myceil(ll a,ll b){return (a+b-1)/b;} template auto vec(const int (&d)[n],const T &init=T()){ if constexpr (id(d,init)); else return init; } #ifdef LOCAL #include #define SWITCH(a,b) (a) #else #define debug(...) static_cast(0) #define debugg(...) static_cast(0) #define SWITCH(a,b) (b) templateostream &operator<<(ostream &os,const pair&p){os<>testcase; for(int i=0;i struct Edge{ int from,to; T weight; int index; Edge(int from_,int to_,T weight_=T(),int index_=-1):from(from_),to(to_),weight(weight_),index(index_){} Edge():from(-1),to(-1),weight(),index(-1){} friend std::ostream &operator<<(std::ostream &os,const Edge&e){ os<<'['; os<<"from:"< struct Tree{ private: int n; std::vectorpar; std::vector>edge; std::vector>g; std::vectorptr; struct tree_range{ using iterator=typename std::vector>::iterator; iterator l,r; iterator begin()const{return l;} iterator end()const{return r;} int size()const{return r-l;} bool empty()const{return !size();} Edge &operator[](int i)const{return l[i];} }; struct const_tree_range{ using iterator=typename std::vector>::const_iterator; iterator l,r; iterator begin()const{return l;} iterator end()const{return r;} int size()const{return r-l;} bool empty()const{return !size();} const Edge &operator[](int i)const{return l[i];} }; public: explicit Tree(int n_):n(n_){ edge.reserve(n-1); } Tree():n(0){} Tree(int n_,const std::vector>&e,bool dir=false):n(n_),edge(e){ if(!dir)build(); else{ par.resize(n,-1); ptr.resize(n+1); for(const Edge&i:edge)ptr[i.from]++,par[i.to]=i.from; for(int i=1;i<=n;i++)ptr[i]+=ptr[i-1]; assert(ptr[n]==n-1); g.resize(n-1); for(const Edge&i:edge)g[--ptr[i.from]]=i; } } template void read(){ for(int i=0;i>u>>v; if constexpr(index)u--,v--; if constexpr(weighted)std::cin>>w; else w=1; edge.emplace_back(u,v,w,i); } build(); } template void readp(){ par.resize(n); par[0]=-1; ptr.resize(n+1); for(int i=1;i>p; if constexpr(index)p--; edge.emplace_back(p,i,1,i-1); par[i]=p; ptr[p]++; } for(int i=1;i<=n;i++)ptr[i]+=ptr[i-1]; g.resize(n-1); for(int i=0;ique; que.push(root); while(!que.empty()){ int x=que.front(); que.pop(); for(const Edge&e:(*this)[x])if(e.to!=par[x]){ par[e.to]=x; edge[e.index]=e; que.push(e.to); } } ptr.resize(n+1); std::fill(ptr.begin(),ptr.end(),0); for(int i=0;i&e:edge)g[--ptr[e.from]]=e; } std::vectorbfs_order()const{ assert(is_directed()); std::vectorbfs(n); int p=0,q=0; bfs[q++]=root(); while(p&e:(*this)[x])bfs[q++]=e.to; } return bfs; } std::vectordfs_order()const{ assert(is_directed()); std::vectorres; res.reserve(n); std::vectorst(n); int p=0; st[p++]=root(); while(p){ int x=st[--p]; res.push_back(x); p+=(*this)[x].size(); for(const Edge&e:(*this)[x])st[--p]=e.to; p+=(*this)[x].size(); } return res; } std::vectorrbfs_order()const{ std::vectorbfs=bfs_order(); std::reverse(bfs.begin(),bfs.end()); return bfs; } void hld(){ assert(is_directed()); std::vectorsub(n); for(int x:rbfs_order()){ sub[x]=1; int mx=-1; for(Edge&e:(*this)[x]){ sub[x]+=sub[e.to]; if(mx,std::vector>in_out_order(){ assert(is_directed()); std::vectorin(n),out(n); int p=0; auto dfs=[&](auto self,int x)->void { in[x]=p++; for(const Edge&e:(*this)[x]){ self(self,e.to); } out[x]=p; }; dfs(dfs,root()); return std::make_pair(in,out); } std::pair>diameter()const{ assert(!is_directed()); static constexpr T inf=std::numeric_limits::max(); std::vectordst(n,inf); dst[0]=0; std::vectorque(n); int p=0,q=1; que[0]=0; while(p&e:(*this)[x])if(dst[e.to]==inf){ dst[e.to]=dst[x]+e.weight; que[q++]=e.to; } } int u=std::max_element(dst.begin(),dst.end())-dst.begin(); std::fill(dst.begin(),dst.end(),inf); dst[u]=0; p=0,q=1; que[0]=u; while(p&e:(*this)[x])if(dst[e.to]==inf){ dst[e.to]=dst[x]+e.weight; que[q++]=e.to; } } int v=std::max_element(dst.begin(),dst.end())-dst.begin(); T weight=dst[v]; std::vectorres; while(u!=v){ res.push_back(v); for(const Edge&e:(*this)[v])if(dst[e.to]& get_edge(int i)const{return edge[i];} inline int parent(int i)const{return par[i];} inline int root()const{return std::find(par.begin(),par.end(),-1)-par.begin();} typename std::vector>::iterator begin(){return edge.begin();} typename std::vector>::iterator end(){return edge.end();} typename std::vector>::const_iterator begin()const{return edge.begin();} typename std::vector>::const_iterator end()const{return edge.end();} }; struct StaticTopTree{ std::vectorleft,right,par,A,B; StaticTopTree(){} template explicit StaticTopTree(Treet){ assert(t.is_directed()); t.hld(); int n=t.size(); left.reserve(n*2-1),right.reserve(n*2-1),par.reserve(n*2-1),A.reserve(n*2-1),B.reserve(n*2-1); left.resize(n,-1),right.resize(n,-1),par.resize(n,-1),A.resize(n),B.resize(n); for(int i=0;istd::pair { std::vector>vs{{0,x}}; while(t[x].size()>=1){ std::priority_queue,std::vector>,std::greater>>que; int heavy=t[x][0].to; que.emplace(0,heavy); for(int i=1;i=2){ auto [d1,v1]=que.top();que.pop(); auto [d2,v2]=que.top();que.pop(); if(B[v2]==heavy)std::swap(d1,d2),std::swap(v1,v2); int nv=left.size(); left.push_back(v1),right.push_back(v2),par.push_back(-1),A.push_back(x),B.push_back(B[v1]); par[v1]=par[v2]=nv; que.emplace(std::max(d1,d2)+1,nv); } vs.push_back(que.top()); while(true){ int sz=vs.size(); if(sz>=3&&(vs[sz-3].first==vs[sz-2].first||vs[sz-3].first<=vs[sz-1].first)){ int nv=left.size(); left.push_back(vs[sz-3].second),right.push_back(vs[sz-2].second),par.push_back(-1),A.push_back(A[vs[sz-3].second]),B.push_back(B[vs[sz-2].second]); par[vs[sz-3].second]=par[vs[sz-2].second]=nv; vs[sz-3].first=std::max(vs[sz-3].first,vs[sz-2].first)+1; vs[sz-3].second=nv; vs[sz-2]=vs[sz-1]; vs.pop_back(); } else if(sz>=2&&vs[sz-2].first<=vs[sz-1].first){ int nv=left.size(); left.push_back(vs[sz-2].second),right.push_back(vs[sz-1].second),par.push_back(-1),A.push_back(A[vs[sz-2].second]),B.push_back(B[vs[sz-1].second]); par[vs[sz-2].second]=par[vs[sz-1].second]=nv; vs[sz-2].first=std::max(vs[sz-2].first,vs[sz-1].first)+1; vs[sz-2].second=nv; vs.pop_back(); } else break; } x=heavy; } while((int)vs.size()>=2){ int sz=vs.size(); int nv=left.size(); left.push_back(vs[sz-2].second),right.push_back(vs[sz-1].second),par.push_back(-1),A.push_back(A[vs[sz-2].second]),B.push_back(B[vs[sz-1].second]); par[vs[sz-2].second]=par[vs[sz-1].second]=nv; vs[sz-2].first=std::max(vs[sz-2].first,vs[sz-1].first)+1; vs[sz-2].second=nv; vs.pop_back(); } return vs[0]; }; dfs(dfs,t.root()); } }; struct ContourQuery{ private: StaticTopTree stt; std::vector>ptr; std::vector>dst; std::vector>vs; std::vectordep; int vsc; public: ContourQuery(){} template ContourQuery(const Tree&t){ assert(!t.is_directed()); int n=t.size(); std::vectorparent(n,-1); { Treet2(t); t2.remove_parent(); for(int i=1;in;){ dep[stt.left[i]]=dep[stt.right[i]]=dep[i]+1; } dst.resize(*std::max_element(dep.begin(),dep.end())+1,std::vector(n,-1)); ptr.resize(n*2-1); std::vectorque(n); int p=0,q=0; std::vectorvis(n,false); vsc=n; vs.resize(n); for(int i=0;i{i}; std::vectorboundaryA_vs; auto dfs=[&](auto self,int v)->std::vector { if(v{v}; } int d=dep[v]; int lv=stt.left[v],rv=stt.right[v]; bool boundaryA=false; std::vectorlch=self(self,lv); p=q=0; boundaryA_vs.clear(); for(int x:lch)if(parent[x]==stt.A[lv])boundaryA_vs.push_back(x); if(stt.A[lv]==stt.A[rv]){ for(int x:boundaryA_vs){ dst[d][x]=1; que[q++]=x; } boundaryA=true; } else{ dst[d][stt.B[lv]]=0; que[q++]=stt.B[lv]; } ptr[lv].resize(2); ptr[lv][0]=vsc; while(p&e:t[x]){ if(vis[e.to]&&dst[d][e.to]==-1){ dst[d][e.to]=dst[d][x]+1; que[q++]=e.to; } else if(!boundaryA&&e.to==stt.A[lv]){ boundaryA=true; que[q++]=~x; } } } for(int i=1;irch=self(self,rv); p=q=0; boundaryA_vs.clear(); for(int x:rch)if(parent[x]==stt.A[rv])boundaryA_vs.push_back(x); for(int x:boundaryA_vs){ dst[d][x]=1; que[q++]=x; } ptr[rv].resize(2); ptr[rv][0]=vsc; while(p&e:t[x])if(vis[e.to]&&dst[d][e.to]==-1){ dst[d][e.to]=dst[d][x]+1; que[q++]=e.to; } } for(int i=1;i&get_vs(int v)const{return vs[v];} std::vector>get_range(int v,int l,int r)const{ std::vector>res; if(l<=0&&1<=r)res.emplace_back(v,v+1); int x=v; while(true){ int par=stt.par[v]; if(par==-1)break; int another=stt.left[par]^stt.right[par]^v; int d=dep[par]; int rtov=dst[d][x]; int nl=std::clamp(l-rtov,0,std::ssize(ptr[another])-1); int nr=std::clamp(r-rtov,0,std::ssize(ptr[another])-1); nl=ptr[another][nl],nr=ptr[another][nr]; if(nl!=nr){ res.emplace_back(nl,nr); } v=par; } return res; } inline int size()const{return vsc;} }; #include #include template constexpr std::enable_if_t::digits<=32,int>msb(T n){return n==0?-1:31-__builtin_clz(n);} template constexpr std::enable_if_t<(std::numeric_limits::digits>32),int>msb(T n){return n==0?-1:63-__builtin_clzll(n);} template constexpr std::enable_if_t::digits<=32,int>lsb(T n){return n==0?-1:__builtin_ctz(n);} template constexpr std::enable_if_t<(std::numeric_limits::digits>32),int>lsb(T n){return n==0?-1:__builtin_ctzll(n);} template constexpr std::enable_if_t,T>floor_pow2(T n){return n==0?0:T(1)< constexpr std::enable_if_t,T>ceil_pow2(T n){return n<=1?1:T(1)<<(msb(n-1)+1);} template constexpr T safe_div(T a,T b){return a/b-(a%b&&(a^b)<0);} template constexpr T safe_ceil(T a,T b){return a/b+(a%b&&(a^b)>0);} template struct BinaryIndexedTree{ private: using S=typename M::S; std::vectordat; int z; public: BinaryIndexedTree(){} explicit BinaryIndexedTree(int n):z(ceil_pow2(n)),dat(n,M::e()){} explicit BinaryIndexedTree(const std::vector&init):z(ceil_pow2((int)init.size())),dat(init){ for(int i=0;i<(int)dat.size();i++){ int j=i+((i+1)&-(i+1)); if(j<(int)dat.size())dat[j]=M::op(dat[i],dat[j]); } } inline void add(int i,S x){ while(i<(int)dat.size()){ dat[i]=M::op(dat[i],x); i+=(i+1)&-(i+1); } } inline S sum(int i)const{ S res=M::e(); while(i>0){ res+=dat[i-1]; i-=i&-i; } return res; } inline S sum(int l,int r)const{ S lp=M::e(),rp=M::e(); while(l=1;i>>=1){ if(res+i<=(int)dat.size()&&dat[res+i-1] struct MonoidAdd{ using S=T; using F=std::nullptr_t; static inline S op(S x,S y){return x+y;} static inline S e(){return 0;} static inline S mapping(F,const S&x,long long){return x;} static inline F composition(F,F){return nullptr;} static inline F id(){return nullptr;} static inline S inverse(S x){return -x;} static inline void revS(S&x){} static inline S pow(S x,long long p){return x*p;} }; void SOLVE(){ int n,q; cin>>n>>q; Tree t(n); t.read(); ContourQuery cq(t); BinaryIndexedTree>BIT(cq.size()); while(q--){ int x,y,z; cin>>x>>y>>z; x--; ll ans=0; for(const int&v:cq.get_vs(x))ans+=BIT.sum(0,v+1); cout<