#include "data_structure/HLD_lazy.hpp"
template<typename T,typename E> class HLD_lazy{ class lazy_segment_tree{ int n=1,sz; T* node; E* lazy; int ids[64]; int idx; void eval(const auto& t){ if(lazy[t]==ee)return; node[t]=h(node[t],lazy[t],n>>(int)(log2(t+1))); if(t<n-1){ lazy[(t<<1)+1]=g(lazy[(t<<1)+1],lazy[t]); lazy[(t<<1)+2]=g(lazy[(t<<1)+2],lazy[t]); } lazy[t]=ee; } void get_eval(auto l,auto r){ l+=n;r+=n; const int lm=(l/(l&-l))>>1; const int rm=(r/(r&-r))>>1; idx=0; while(r>l){ if(r<=rm&&r)ids[idx++]=r-1; if(l<=lm&&l)ids[idx++]=l-1; l>>=1;r>>=1; } while(l){ ids[idx++]=l-1; l>>=1; } } public: lazy_segment_tree(const vector<T>& v):sz(v.size()){ while(n<(int)v.size())n<<=1; node=new T[(n<<1)-1]; lazy=new E[(n<<1)-1]; for(int i=(int)v.size()+n-1;i<(n<<1)-1;i++)node[i]=et; for(int i=0;i<(n<<1)-1;i++)lazy[i]=ee; 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]); } lazy_segment_tree(const auto& sz):sz(sz){ while(n<(int)sz)n<<=1; node=new T[(n<<1)-1]; lazy=new E[(n<<1)-1]; for(int i=0;i<(n<<1)-1;i++)node[i]=et; for(int i=0;i<(n<<1)-1;i++)lazy[i]=ee; } void update(auto l,auto r,E val){ if(l>r)swap(l,r); r++; get_eval(l,r); for(int i=idx-1;i>=0;i--)eval(ids[i]); l+=n;r+=n; while(l<r){ if(l&1){lazy[l-1]=g(lazy[l-1],val);eval(l-1);++l;} if(r&1){--r;lazy[r-1]=g(lazy[r-1],val);eval(r-1);} l>>=1;r>>=1; } for(int i=0;i<idx;i++){ eval((ids[i]<<1)+1); eval((ids[i]<<1)+2); node[ids[i]]=f(node[(ids[i]<<1)+1],node[(ids[i]<<1)+2]); } } T get(auto l,auto r){ if(l>r)swap(l,r); r++; get_eval(l,r); for(int i=idx-1;i>=0;i--)eval(ids[i]); l+=n;r+=n; T res=et; while(l<r){ if(l&1){eval(l-1);res=f(res,node[l-1]);l++;} if(r&1){--r;eval(r-1);res=f(res,node[r-1]);} l>>=1;r>>=1; } return res; } }; 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(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); stack<tuple<int,int>>stk; stk.emplace(root,-1); int idx=0; par[root]=root; head[root]=root; while(!stk.empty()){ int n,p; tie(n,p)=stk.top(); stk.pop(); vertex[n]=idx++; int mx=0,heavy=-1; for(auto t:v[n])if(t!=p&&mx<sz[t]){ mx=sz[t]; heavy=t; } for(auto t:v[n]){ if(t!=heavy&&t!=p){ par[t]=n; head[t]=t; stk.emplace(t,n); } } if(heavy!=-1){ par[heavy]=par[n]; head[heavy]=head[n]; stk.emplace(heavy,n); } } } int* sz; int* vertex; int* par; int* head; lazy_segment_tree* seg; public: HLD_lazy(const auto& v,int root=0){ make(v,root); seg=new lazy_segment_tree(v.size()); } HLD_lazy(const auto& v,const auto& a,int root=0){ vector<T>tmp(v.size()); make(v,root); for(int i=0;i<(int)v.size();i++){ tmp[vertex[i]]=a[i]; } seg=new lazy_segment_tree(tmp); } int lca(auto l,auto r){ while(1){ if(head[l]==head[r])return sz[l]>sz[r]?l:r; else if(sz[head[l]]>sz[head[r]])r=par[r]; else l=par[l]; } } inline void update_vertex(auto u,E x){ seg->update(vertex[u],vertex[u],x); } inline T get_vertex(auto u){ return seg->get(vertex[u],vertex[u]); } inline void update_subtree(auto u,E x){ seg->update(vertex[u],vertex[u]+sz[u]-1); } inline T get_subtree(auto u){ return seg->get(vertex[u],vertex[u]+sz[u]-1); } void update_path(auto u,auto v,E x){ while(1){ if(head[u]==head[v]){ seg->update(vertex[u],vertex[v],x); break; } else if(sz[head[u]]>sz[head[v]]){ seg->update(vertex[v],vertex[head[v]],x); v=par[v]; } else{ seg->update(vertex[u],vertex[head[u]],x); u=par[u]; } } } T get_path(auto u,auto v){ T res=et; while(1){ if(head[u]==head[v]){ return f(res,seg->get(vertex[u],vertex[v])); } else 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]; } } } protected: constexpr static T et=0; constexpr static E ee=0; constexpr static T f(const T& a,const T& b){ return a+b; } constexpr static T h(const T& a,const E& b,const auto& sz){ return a+b*sz; } constexpr static E g(const E& a,const E& b){ return a+b; } constexpr static auto update(auto a,auto b){return b==ee?a:b;} };
#line 1 "data_structure/HLD_lazy.hpp" template<typename T,typename E> class HLD_lazy{ class lazy_segment_tree{ int n=1,sz; T* node; E* lazy; int ids[64]; int idx; void eval(const auto& t){ if(lazy[t]==ee)return; node[t]=h(node[t],lazy[t],n>>(int)(log2(t+1))); if(t<n-1){ lazy[(t<<1)+1]=g(lazy[(t<<1)+1],lazy[t]); lazy[(t<<1)+2]=g(lazy[(t<<1)+2],lazy[t]); } lazy[t]=ee; } void get_eval(auto l,auto r){ l+=n;r+=n; const int lm=(l/(l&-l))>>1; const int rm=(r/(r&-r))>>1; idx=0; while(r>l){ if(r<=rm&&r)ids[idx++]=r-1; if(l<=lm&&l)ids[idx++]=l-1; l>>=1;r>>=1; } while(l){ ids[idx++]=l-1; l>>=1; } } public: lazy_segment_tree(const vector<T>& v):sz(v.size()){ while(n<(int)v.size())n<<=1; node=new T[(n<<1)-1]; lazy=new E[(n<<1)-1]; for(int i=(int)v.size()+n-1;i<(n<<1)-1;i++)node[i]=et; for(int i=0;i<(n<<1)-1;i++)lazy[i]=ee; 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]); } lazy_segment_tree(const auto& sz):sz(sz){ while(n<(int)sz)n<<=1; node=new T[(n<<1)-1]; lazy=new E[(n<<1)-1]; for(int i=0;i<(n<<1)-1;i++)node[i]=et; for(int i=0;i<(n<<1)-1;i++)lazy[i]=ee; } void update(auto l,auto r,E val){ if(l>r)swap(l,r); r++; get_eval(l,r); for(int i=idx-1;i>=0;i--)eval(ids[i]); l+=n;r+=n; while(l<r){ if(l&1){lazy[l-1]=g(lazy[l-1],val);eval(l-1);++l;} if(r&1){--r;lazy[r-1]=g(lazy[r-1],val);eval(r-1);} l>>=1;r>>=1; } for(int i=0;i<idx;i++){ eval((ids[i]<<1)+1); eval((ids[i]<<1)+2); node[ids[i]]=f(node[(ids[i]<<1)+1],node[(ids[i]<<1)+2]); } } T get(auto l,auto r){ if(l>r)swap(l,r); r++; get_eval(l,r); for(int i=idx-1;i>=0;i--)eval(ids[i]); l+=n;r+=n; T res=et; while(l<r){ if(l&1){eval(l-1);res=f(res,node[l-1]);l++;} if(r&1){--r;eval(r-1);res=f(res,node[r-1]);} l>>=1;r>>=1; } return res; } }; 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(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); stack<tuple<int,int>>stk; stk.emplace(root,-1); int idx=0; par[root]=root; head[root]=root; while(!stk.empty()){ int n,p; tie(n,p)=stk.top(); stk.pop(); vertex[n]=idx++; int mx=0,heavy=-1; for(auto t:v[n])if(t!=p&&mx<sz[t]){ mx=sz[t]; heavy=t; } for(auto t:v[n]){ if(t!=heavy&&t!=p){ par[t]=n; head[t]=t; stk.emplace(t,n); } } if(heavy!=-1){ par[heavy]=par[n]; head[heavy]=head[n]; stk.emplace(heavy,n); } } } int* sz; int* vertex; int* par; int* head; lazy_segment_tree* seg; public: HLD_lazy(const auto& v,int root=0){ make(v,root); seg=new lazy_segment_tree(v.size()); } HLD_lazy(const auto& v,const auto& a,int root=0){ vector<T>tmp(v.size()); make(v,root); for(int i=0;i<(int)v.size();i++){ tmp[vertex[i]]=a[i]; } seg=new lazy_segment_tree(tmp); } int lca(auto l,auto r){ while(1){ if(head[l]==head[r])return sz[l]>sz[r]?l:r; else if(sz[head[l]]>sz[head[r]])r=par[r]; else l=par[l]; } } inline void update_vertex(auto u,E x){ seg->update(vertex[u],vertex[u],x); } inline T get_vertex(auto u){ return seg->get(vertex[u],vertex[u]); } inline void update_subtree(auto u,E x){ seg->update(vertex[u],vertex[u]+sz[u]-1); } inline T get_subtree(auto u){ return seg->get(vertex[u],vertex[u]+sz[u]-1); } void update_path(auto u,auto v,E x){ while(1){ if(head[u]==head[v]){ seg->update(vertex[u],vertex[v],x); break; } else if(sz[head[u]]>sz[head[v]]){ seg->update(vertex[v],vertex[head[v]],x); v=par[v]; } else{ seg->update(vertex[u],vertex[head[u]],x); u=par[u]; } } } T get_path(auto u,auto v){ T res=et; while(1){ if(head[u]==head[v]){ return f(res,seg->get(vertex[u],vertex[v])); } else 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]; } } } protected: constexpr static T et=0; constexpr static E ee=0; constexpr static T f(const T& a,const T& b){ return a+b; } constexpr static T h(const T& a,const E& b,const auto& sz){ return a+b*sz; } constexpr static E g(const E& a,const E& b){ return a+b; } constexpr static auto update(auto a,auto b){return b==ee?a:b;} };