C++实现树链剖分

admin

[mw_shl_code=cpp,true]#include<bits/stdc++.h>
using namespace std;
const int maxN=1e5;
int n,q,root,mod;
int wt[maxN+5];//临时存储结点权值.
struct Segment_Tree{
        int val[(maxN<<2)+5],laz[(maxN<<2)+5],ans;
        void push_up(int u){val=(val[u<<1]+val[u<<1|1])%mod;}
        void push_down(int u,int l,int r){
                if(!laz)return;
                laz[u<<1]=(laz[u<<1]+laz)%mod,laz[u<<1|1]=(laz[u<<1|1]+laz)%mod;
                int mid=l+r>>1;val[u<<1]=(val[u<<1]+(mid-l+1)*laz)%mod,val[u<<1|1]=(val[u<<1|1]+(r-mid)*laz)%mod;
                laz=0;
        }
        void build(int u,int l,int r){
                if(l==r){val=wt[l]%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[maxN+5],fa[maxN+5],dep[maxN+5],siz[maxN+5],wson[maxN+5],top[maxN+5],seg[maxN+5],lf[maxN+5],cnt;//用lf[]数组记录是否是叶子节点.
        int stot[maxN+5],vis[maxN+5];vector<int>node[maxN+5];
        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[pre]+1,siz=1;int maxson(-1);//记得给siz初始化.
                if(stot==1&&vis[node[1]])lf=1;//记录是否是叶子结点.
                for(int i(1);i<=stot;++i){
                        int v=node;if(vis[v])continue;
                        dfs1(v,u),siz+=siz[v];
                        if(siz[v]>maxson)maxson=siz[v],wson=v;
                }
        }
        void dfs2(int u,int topf){
                vis=1,seg=++cnt,wt[cnt]=w,top=topf;
                if(lf)return;//注意这里不能用儿子的个数来判断.
                dfs2(wson,topf);
                for(int i(1);i<=stot;++i){int v=node;if(vis[v])continue;dfs2(v,v);}
        }
        void updchain(int u,int v,int w){
                while(top!=top[v]){
                        if(dep[top]<dep[top[v]])swap(u,v);
                        sgmnttr.update(1,1,n,seg[top],seg,w),u=fa[top];
                }
                if(dep>dep[v])swap(u,v);
                sgmnttr.update(1,1,n,seg,seg[v],w);
        }
        int qrychain(int u,int v){
                int ans(0);
                while(top!=top[v]){
                        if(dep[top]<dep[top[v]])swap(u,v);
                        sgmnttr.ans=0,sgmnttr.query(1,1,n,seg[top],seg),ans=(ans+sgmnttr.ans)%mod,u=fa[top];
                }
                if(dep>dep[v])swap(u,v);
                sgmnttr.ans=0,sgmnttr.query(1,1,n,seg,seg[v]),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;
}[/mw_shl_code]