C++实现树链剖分
#include<bits/stdc++.h>using namespace std;
const int maxN=1e5;
int n,q,root,mod;
int wt;//临时存储结点权值.
struct Segment_Tree{
int val[(maxN<<2)+5],laz[(maxN<<2)+5],ans;
void push_up(int u){val=(val+val)%mod;}
void push_down(int u,int l,int r){
if(!laz)return;
laz=(laz+laz)%mod,laz=(laz+laz)%mod;
int mid=l+r>>1;val=(val+(mid-l+1)*laz)%mod,val=(val+(r-mid)*laz)%mod;
laz=0;
}
void build(int u,int l,int r){
if(l==r){val=wt%mod;return;}
int mid=l+r>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);
push_up(u);
}
void update(int u,int l,int r,int x,int y,int plus){
if(x<=l&&r<=y){val=(val+(r-l+1)*plus)%mod,laz=(laz+plus)%mod;return;}//判断时不要写反了.
push_down(u,l,r);
int mid=l+r>>1;if(x<=mid)update(u<<1,l,mid,x,y,plus);if(y>mid)update(u<<1|1,mid+1,r,x,y,plus);
push_up(u);
}
void query(int u,int l,int r,int x,int y){
if(x<=l&&r<=y){ans=(ans+val)%mod;return;}
push_down(u,l,r);
int mid=l+r>>1;if(x<=mid)query(u<<1,l,mid,x,y);if(y>mid)query(u<<1|1,mid+1,r,x,y);
}
}sgmnttr;
struct Cut_Tree{
int w,fa,dep,siz,wson,top,seg,lf,cnt;//用lf[]数组记录是否是叶子节点.
int stot,vis;vector<int>node;
void add(int u,int v){if(!stot)node.push_back(0);++stot,node.push_back(v);}
void dfs1(int u,int pre){
vis=1,fa=pre,dep=dep+1,siz=1;int maxson(-1);//记得给siz初始化.
if(stot==1&&vis])lf=1;//记录是否是叶子结点.
for(int i(1);i<=stot;++i){
int v=node;if(vis)continue;
dfs1(v,u),siz+=siz;
if(siz>maxson)maxson=siz,wson=v;
}
}
void dfs2(int u,int topf){
vis=1,seg=++cnt,wt=w,top=topf;
if(lf)return;//注意这里不能用儿子的个数来判断.
dfs2(wson,topf);
for(int i(1);i<=stot;++i){int v=node;if(vis)continue;dfs2(v,v);}
}
void updchain(int u,int v,int w){
while(top!=top){
if(dep]<dep])swap(u,v);
sgmnttr.update(1,1,n,seg],seg,w),u=fa];
}
if(dep>dep)swap(u,v);
sgmnttr.update(1,1,n,seg,seg,w);
}
int qrychain(int u,int v){
int ans(0);
while(top!=top){
if(dep]<dep])swap(u,v);
sgmnttr.ans=0,sgmnttr.query(1,1,n,seg],seg),ans=(ans+sgmnttr.ans)%mod,u=fa];
}
if(dep>dep)swap(u,v);
sgmnttr.ans=0,sgmnttr.query(1,1,n,seg,seg),ans=(ans+sgmnttr.ans)%mod;
return ans;
}
void updson(int u,int w){sgmnttr.update(1,1,n,seg,seg+siz-1,w);}
int qryson(int u){sgmnttr.ans=0,sgmnttr.query(1,1,n,seg,seg+siz-1);return sgmnttr.ans;}
}cttr;
int main(){
scanf("%d%d%d%d",&n,&q,&root,&mod);
for(int i(1);i<=n;++i)scanf("%d",&cttr.w),cttr.w%=mod;
int u,v;for(int i(1);i<=n-1;++i)scanf("%d%d",&u,&v),cttr.add(u,v),cttr.add(v,u);
cttr.dfs1(root,0),memset(cttr.vis,0,sizeof(cttr.vis)),cttr.dfs2(root,root),sgmnttr.build(1,1,n);
for(int i(1);i<=q;++i){
int op,u,v,w;scanf("%d",&op);
if(op==1)scanf("%d%d%d",&u,&v,&w),cttr.updchain(u,v,w%mod);
if(op==2)scanf("%d%d",&u,&v),printf("%d\n",cttr.qrychain(u,v));
if(op==3)scanf("%d%d",&u,&w),cttr.updson(u,w%mod);
if(op==4)scanf("%d",&u),printf("%d\n",cttr.qryson(u));
}
return 0;
}
页:
[1]