結果
問題 |
No.1038 TreeAddQuery
|
ユーザー |
![]() |
提出日時 | 2025-07-08 13:31:05 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 949 ms / 4,000 ms |
コード長 | 19,232 bytes |
コンパイル時間 | 4,455 ms |
コンパイル使用メモリ | 331,792 KB |
実行使用メモリ | 76,212 KB |
最終ジャッジ日時 | 2025-07-08 13:31:33 |
合計ジャッジ時間 | 21,574 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll=long long; using ull=unsigned long long; using P=pair<ll,ll>; template<typename T>using minque=priority_queue<T,vector<T>,greater<T>>; template<typename T>bool chmax(T &a,const T &b){return (a<b?(a=b,true):false);} template<typename T>bool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} template<typename T1,typename T2>istream &operator>>(istream &is,pair<T1,T2>&p){is>>p.first>>p.second;return is;} template<typename T1,typename T2,typename T3>istream &operator>>(istream &is,tuple<T1,T2,T3>&a){is>>std::get<0>(a)>>std::get<1>(a)>>std::get<2>(a);return is;} template<typename T,size_t n>istream &operator>>(istream &is,array<T,n>&a){for(auto&i:a)is>>i;return is;} template<typename T>istream &operator>>(istream &is,vector<T> &a){for(auto &i:a)is>>i;return is;} template<typename T1,typename T2>void operator++(pair<T1,T2>&a,int n){a.first++,a.second++;} template<typename T1,typename T2>void operator--(pair<T1,T2>&a,int n){a.first--,a.second--;} template<typename T>void operator++(vector<T>&a,int n){for(auto &i:a)i++;} template<typename T>void operator--(vector<T>&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<void>(0) #define yn(x) cout<<((x)?"Yes\n":"No\n") #define uniq(x) sort(all(x)),x.erase(unique(all(x)),x.end()) template<typename T> inline int fkey(vector<T>&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<typename T,size_t n,size_t id=0> auto vec(const int (&d)[n],const T &init=T()){ if constexpr (id<n)return vector(d[id],vec<T,n,id+1>(d,init)); else return init; } #ifdef LOCAL #include<debug.h> #define SWITCH(a,b) (a) #else #define debug(...) static_cast<void>(0) #define debugg(...) static_cast<void>(0) #define SWITCH(a,b) (b) template<typename T1,typename T2>ostream &operator<<(ostream &os,const pair<T1,T2>&p){os<<p.first<<' '<<p.second;return os;} #endif struct Timer{ clock_t start; Timer(){ start=clock(); ios::sync_with_stdio(false); cin.tie(nullptr); cout<<fixed<<setprecision(16); } inline double now(){return (double)(clock()-start)/1000;} #ifdef LOCAL ~Timer(){ cerr<<"time:"; cerr<<now(); cerr<<"ms\n"; } #endif }timer; void SOLVE(); int main(){ int testcase=1; //cin>>testcase; for(int i=0;i<testcase;i++){ SOLVE(); } } template<typename T=int> 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:"<<e.from; os<<"to:"<<e.to; os<<"weight:"<<e.weight; os<<"index:"<<e.index; os<<']'; return os; } }; template<typename T=int> struct Tree{ private: int n; std::vector<int>par; std::vector<Edge<T>>edge; std::vector<Edge<T>>g; std::vector<int>ptr; struct tree_range{ using iterator=typename std::vector<Edge<T>>::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<T> &operator[](int i)const{return l[i];} }; struct const_tree_range{ using iterator=typename std::vector<Edge<T>>::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<T> &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<Edge<T>>&e,bool dir=false):n(n_),edge(e){ if(!dir)build(); else{ par.resize(n,-1); ptr.resize(n+1); for(const Edge<T>&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<T>&i:edge)g[--ptr[i.from]]=i; } } template<bool weighted=false,bool index=1> void read(){ for(int i=0;i<n-1;i++){ int u,v; T w=T(); std::cin>>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<bool index=1> void readp(){ par.resize(n); par[0]=-1; ptr.resize(n+1); for(int i=1;i<n;i++){ int p; std::cin>>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;i<n-1;i++){ g[--ptr[edge[i].from]]=edge[i]; } } void add_edge(int u,int v){edge.emplace_back(u,v,1,edge.size());} void add_edge(int u,int v,T w){edge.emplace_back(u,v,w,edge.size());} void add_edge(int u,int v,T w,int idx){edge.emplace_back(u,v,w,idx);} inline bool is_directed()const{return !par.empty();} void build(){ ptr.resize(n+1,0); for(auto&&[u,v,w,i]:edge)ptr[u]++,ptr[v]++; for(int i=1;i<=n;i++)ptr[i]+=ptr[i-1]; assert(ptr[n]==n*2-2); g.resize(n*2-2); par.clear(); for(auto&&[u,v,w,i]:edge){ g[--ptr[u]]=Edge(u,v,w,i); g[--ptr[v]]=Edge(v,u,w,i); } } void remove_parent(int root=0){ edge.resize(n-1); par.resize(n); par[root]=-1; std::queue<int>que; que.push(root); while(!que.empty()){ int x=que.front(); que.pop(); for(const Edge<T>&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<n-1;i++)ptr[edge[i].from]++; for(int i=1;i<=n;i++)ptr[i]+=ptr[i-1]; g.resize(ptr[n]); for(const Edge<T>&e:edge)g[--ptr[e.from]]=e; } std::vector<int>bfs_order()const{ assert(is_directed()); std::vector<int>bfs(n); int p=0,q=0; bfs[q++]=root(); while(p<q){ int x=bfs[p++]; for(const Edge<T>&e:(*this)[x])bfs[q++]=e.to; } return bfs; } std::vector<int>dfs_order()const{ assert(is_directed()); std::vector<int>res; res.reserve(n); std::vector<int>st(n); int p=0; st[p++]=root(); while(p){ int x=st[--p]; res.push_back(x); p+=(*this)[x].size(); for(const Edge<T>&e:(*this)[x])st[--p]=e.to; p+=(*this)[x].size(); } return res; } std::vector<int>rbfs_order()const{ std::vector<int>bfs=bfs_order(); std::reverse(bfs.begin(),bfs.end()); return bfs; } void hld(){ assert(is_directed()); std::vector<int>sub(n); for(int x:rbfs_order()){ sub[x]=1; int mx=-1; for(Edge<T>&e:(*this)[x]){ sub[x]+=sub[e.to]; if(mx<sub[e.to]){ mx=sub[e.to]; std::swap((*this)[x][0],e); } } } } std::pair<std::vector<int>,std::vector<int>>in_out_order(){ assert(is_directed()); std::vector<int>in(n),out(n); int p=0; auto dfs=[&](auto self,int x)->void { in[x]=p++; for(const Edge<T>&e:(*this)[x]){ self(self,e.to); } out[x]=p; }; dfs(dfs,root()); return std::make_pair(in,out); } std::pair<T,std::vector<int>>diameter()const{ assert(!is_directed()); static constexpr T inf=std::numeric_limits<T>::max(); std::vector<T>dst(n,inf); dst[0]=0; std::vector<int>que(n); int p=0,q=1; que[0]=0; while(p<q){ int x=que[p++]; for(const Edge<T>&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<q){ int x=que[p++]; for(const Edge<T>&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::vector<int>res; while(u!=v){ res.push_back(v); for(const Edge<T>&e:(*this)[v])if(dst[e.to]<dst[v]){ v=e.to; break; } } res.push_back(u); return std::make_pair(weight,res); } int size()const{return n;} tree_range operator[](int i){return tree_range{g.begin()+ptr[i],g.begin()+ptr[i+1]};} const_tree_range operator[](int i)const{return const_tree_range{g.begin()+ptr[i],g.begin()+ptr[i+1]};} const Edge<T>& 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<Edge<T>>::iterator begin(){return edge.begin();} typename std::vector<Edge<T>>::iterator end(){return edge.end();} typename std::vector<Edge<T>>::const_iterator begin()const{return edge.begin();} typename std::vector<Edge<T>>::const_iterator end()const{return edge.end();} }; struct StaticTopTree{ std::vector<int>left,right,par,A,B; StaticTopTree(){} template<typename T> explicit StaticTopTree(Tree<T>t){ 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;i<n;i++){ A[i]=t.parent(i); B[i]=i; } auto dfs=[&](auto self,int x)->std::pair<int,int> { std::vector<std::pair<int,int>>vs{{0,x}}; while(t[x].size()>=1){ std::priority_queue<std::pair<int,int>,std::vector<std::pair<int,int>>,std::greater<std::pair<int,int>>>que; int heavy=t[x][0].to; que.emplace(0,heavy); for(int i=1;i<t[x].size();i++)que.push(self(self,t[x][i].to)); while((int)que.size()>=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<std::vector<int>>ptr; std::vector<std::vector<int>>dst; std::vector<std::vector<int>>vs; std::vector<int>dep; int vsc; public: ContourQuery(){} template<typename T> ContourQuery(const Tree<T>&t){ assert(!t.is_directed()); int n=t.size(); std::vector<int>parent(n,-1); { Tree<T>t2(t); t2.remove_parent(); for(int i=1;i<n;i++)parent[i]=t2.parent(i); stt=StaticTopTree(std::move(t2)); } dep.resize(n*2-1); for(int i=n*2-1;i-->n;){ dep[stt.left[i]]=dep[stt.right[i]]=dep[i]+1; } dst.resize(*std::max_element(dep.begin(),dep.end())+1,std::vector<int>(n,-1)); ptr.resize(n*2-1); std::vector<int>que(n); int p=0,q=0; std::vector<bool>vis(n,false); vsc=n; vs.resize(n); for(int i=0;i<n;i++)vs[i]=std::vector<int>{i}; std::vector<int>boundaryA_vs; auto dfs=[&](auto self,int v)->std::vector<int> { if(v<n){ vis[v]=true; return std::vector<int>{v}; } int d=dep[v]; int lv=stt.left[v],rv=stt.right[v]; bool boundaryA=false; std::vector<int>lch=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<q){ int x=que[p++]; if(x<0){ x=~x; for(int y:boundaryA_vs)if(x!=y){ dst[d][y]=dst[d][x]+2; que[q++]=y; } continue; } while(std::ssize(ptr[lv])<=dst[d][x]+1)ptr[lv].push_back(0); ptr[lv][dst[d][x]+1]++; vs[x].push_back(vsc++); for(const Edge<T>&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;i<std::ssize(ptr[lv]);i++)ptr[lv][i]+=ptr[lv][i-1]; for(int x:lch)vis[x]=false; vsc=ptr[lv].back(); std::vector<int>rch=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<q){ int x=que[p++]; if(std::ssize(ptr[rv])==dst[d][x]+1)ptr[rv].push_back(0); ptr[rv][dst[d][x]+1]++; vs[x].push_back(vsc++); for(const Edge<T>&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<std::ssize(ptr[rv]);i++)ptr[rv][i]+=ptr[rv][i-1]; vsc=ptr[rv].back(); for(int x:lch)vis[x]=true; if(std::ssize(lch)<std::ssize(rch))std::swap(lch,rch); lch.insert(lch.end(),rch.begin(),rch.end()); return lch; }; dfs(dfs,n*2-2); } const std::vector<int>&get_vs(int v)const{return vs[v];} std::vector<std::pair<int,int>>get_range(int v,int l,int r)const{ std::vector<std::pair<int,int>>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<int>(l-rtov,0,std::ssize(ptr[another])-1); int nr=std::clamp<int>(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<type_traits> #include<concepts> template<typename T> constexpr std::enable_if_t<std::numeric_limits<T>::digits<=32,int>msb(T n){return n==0?-1:31-__builtin_clz(n);} template<typename T> constexpr std::enable_if_t<(std::numeric_limits<T>::digits>32),int>msb(T n){return n==0?-1:63-__builtin_clzll(n);} template<typename T> constexpr std::enable_if_t<std::numeric_limits<T>::digits<=32,int>lsb(T n){return n==0?-1:__builtin_ctz(n);} template<typename T> constexpr std::enable_if_t<(std::numeric_limits<T>::digits>32),int>lsb(T n){return n==0?-1:__builtin_ctzll(n);} template<typename T> constexpr std::enable_if_t<std::is_integral_v<T>,T>floor_pow2(T n){return n==0?0:T(1)<<msb(n);} template<typename T> constexpr std::enable_if_t<std::is_integral_v<T>,T>ceil_pow2(T n){return n<=1?1:T(1)<<(msb(n-1)+1);} template<std::integral T> constexpr T safe_div(T a,T b){return a/b-(a%b&&(a^b)<0);} template<std::integral T> constexpr T safe_ceil(T a,T b){return a/b+(a%b&&(a^b)>0);} template<typename M> struct BinaryIndexedTree{ private: using S=typename M::S; std::vector<S>dat; int z; public: BinaryIndexedTree(){} explicit BinaryIndexedTree(int n):z(ceil_pow2(n)),dat(n,M::e()){} explicit BinaryIndexedTree(const std::vector<S>&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<r){ rp=M::op(dat[r-1],rp); r-=r&-r; } while(r<l){ lp=M::op(dat[l-1],lp); l-=l&-l; } return M::op(M::inverse(lp),rp); } int lower_bound(S k)const{ int res=0; for(int i=z;i>=1;i>>=1){ if(res+i<=(int)dat.size()&&dat[res+i-1]<k){ k-=dat[res+i-1]; res+=i; } } return res; } friend std::ostream &operator<<(std::ostream &os,const BinaryIndexedTree&bit){ os<<"{"; for(int i=0;i<(int)bit.dat.size();i++)os<<bit.sum(i,i+1)<<",}"[i+1==(int)bit.dat.size()]; if(bit.dat.empty())os<<"}"; return os; } }; template<typename T=int> 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<MonoidAdd<ll>>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<<ans<<'\n'; for(auto [l,r]:cq.get_range(x,0,y+1)){ BIT.add(l,z); BIT.add(r,-z); } } }