#include "data_structure/HLD_seg.hpp"
template<typename T> class HLD_seg{ class segment{ T* node; int n=1; public: segment(int sz){ while(n<sz)n<<=1; node=new T[(n<<1)-1]; for(int i=0;i<(n<<1)-1;i++)node[i]=e; } segment(const vector<T>& v){ while(n<(int)v.size())n<<=1; node=new T[(n<<1)-1]; for(int i=0;i<(int)v.size();i++)node[i+n-1]=v[i]; for(int i=n-2;i>=0;i--)node[i]=f(node[(i<<1)+1],node[(i<<1)+2]); } T get(auto l,auto r){ if(l>r)swap(l,r); l+=n;r+=n+1; T s=e; while(l<r){ if(l&1)s=f(s,node[l++-1]); if(r&1)s=f(s,node[--r-1]); l>>=1;r>>=1; } return s; } void update(auto t,T val){ t+=n-1; while(1){ node[t]=f(node[t],val); t=(t-1)>>1; if(!t)break; } } }; int child_size(const auto& v,int n,int p){ int cnt=0; for(auto t:v[n]){ if(t!=p)cnt+=child_size(v,t,n); } return sz[n]=cnt+1; } void make_hld(const auto&v,int n,int p){ static int idx=0; vertex[n]=idx++; int mx=0,heavy=-1; for(auto t:v[n])if(t!=p&&mx<sz[t]){ mx=sz[t]; heavy=t; } if(heavy!=-1){ par[heavy]=par[n]; head[heavy]=head[n]; make_hld(v,heavy,n); } for(auto t:v[n]){ if(t!=heavy&&t!=p){ par[t]=n; head[t]=t; make_hld(v,t,n); } } } int* sz; int* vertex; int* par; int* head; segment* seg; public: HLD_seg(const auto& v,int root=0){ make(v,root); seg=new segment(v.size()); } HLD_seg(const auto& v,const auto& a,int root=0){ make(v,root); vector<T>tmp(v.size()); for(int i=0;i<(int)v.size();i++){ tmp[vertex[i]]=a[i]; } seg=new segment(tmp); } void make(const auto& v,int root){ sz=new int[v.size()]; vertex=new int[v.size()]; par=new int[v.size()]; head=new int[v.size()]; child_size(v,root,-1); par[root]=root; head[root]=root; make_hld(v,root,-1); } int lca(auto l,auto r){ while(head[l]!=head[r]){ if(sz[head[l]]>sz[head[r]])r=par[r]; else l=par[l]; } return sz[l]>sz[r]?l:r; } inline void update(auto t,T x){ seg->update(vertex[t],x); } T get(auto u,auto v){ T res=e; while(head[u]!=head[v]){ if(sz[head[u]]>sz[head[v]]){ res=f(res,seg->get(vertex[v],vertex[head[v]])); v=par[v]; } else{ res=f(res,seg->get(vertex[u],vertex[head[u]])); u=par[u]; } } return f(res,seg->get(vertex[u],vertex[v])); } inline T get_subtree(auto u){ return seg->get(vertex[u],vertex[u]+sz[u]-1); } protected: constexpr static T e=0; constexpr static T f(const T& s,const T& t){ return s+t; } };
#line 1 "data_structure/HLD_seg.hpp" template<typename T> class HLD_seg{ class segment{ T* node; int n=1; public: segment(int sz){ while(n<sz)n<<=1; node=new T[(n<<1)-1]; for(int i=0;i<(n<<1)-1;i++)node[i]=e; } segment(const vector<T>& v){ while(n<(int)v.size())n<<=1; node=new T[(n<<1)-1]; for(int i=0;i<(int)v.size();i++)node[i+n-1]=v[i]; for(int i=n-2;i>=0;i--)node[i]=f(node[(i<<1)+1],node[(i<<1)+2]); } T get(auto l,auto r){ if(l>r)swap(l,r); l+=n;r+=n+1; T s=e; while(l<r){ if(l&1)s=f(s,node[l++-1]); if(r&1)s=f(s,node[--r-1]); l>>=1;r>>=1; } return s; } void update(auto t,T val){ t+=n-1; while(1){ node[t]=f(node[t],val); t=(t-1)>>1; if(!t)break; } } }; int child_size(const auto& v,int n,int p){ int cnt=0; for(auto t:v[n]){ if(t!=p)cnt+=child_size(v,t,n); } return sz[n]=cnt+1; } void make_hld(const auto&v,int n,int p){ static int idx=0; vertex[n]=idx++; int mx=0,heavy=-1; for(auto t:v[n])if(t!=p&&mx<sz[t]){ mx=sz[t]; heavy=t; } if(heavy!=-1){ par[heavy]=par[n]; head[heavy]=head[n]; make_hld(v,heavy,n); } for(auto t:v[n]){ if(t!=heavy&&t!=p){ par[t]=n; head[t]=t; make_hld(v,t,n); } } } int* sz; int* vertex; int* par; int* head; segment* seg; public: HLD_seg(const auto& v,int root=0){ make(v,root); seg=new segment(v.size()); } HLD_seg(const auto& v,const auto& a,int root=0){ make(v,root); vector<T>tmp(v.size()); for(int i=0;i<(int)v.size();i++){ tmp[vertex[i]]=a[i]; } seg=new segment(tmp); } void make(const auto& v,int root){ sz=new int[v.size()]; vertex=new int[v.size()]; par=new int[v.size()]; head=new int[v.size()]; child_size(v,root,-1); par[root]=root; head[root]=root; make_hld(v,root,-1); } int lca(auto l,auto r){ while(head[l]!=head[r]){ if(sz[head[l]]>sz[head[r]])r=par[r]; else l=par[l]; } return sz[l]>sz[r]?l:r; } inline void update(auto t,T x){ seg->update(vertex[t],x); } T get(auto u,auto v){ T res=e; while(head[u]!=head[v]){ if(sz[head[u]]>sz[head[v]]){ res=f(res,seg->get(vertex[v],vertex[head[v]])); v=par[v]; } else{ res=f(res,seg->get(vertex[u],vertex[head[u]])); u=par[u]; } } return f(res,seg->get(vertex[u],vertex[v])); } inline T get_subtree(auto u){ return seg->get(vertex[u],vertex[u]+sz[u]-1); } protected: constexpr static T e=0; constexpr static T f(const T& s,const T& t){ return s+t; } };