【模板】轻重链剖分+线段树

    科技2024-11-12  12

    题目链接

    题解:

    #include <bits/stdc++.h> #define ll long long using namespace std; int next[500001]; int head[500001]; int to[500001]; int cnt; int son[500001];//求重儿子 int fa[500001];//父亲结点 int tol[500001];//子节点个数 int dep[500001];//深度 int dfn[500001];//dfs序列 int rnk[500001];//dfs序列所对应的元素 int top[500001];//链的顶端 int treev[4*500001]; int value[500001]; int n,m,r,p; int lazy[4*500001]; void pushdown(int l,int r,int x); int query(int l,int r,int lx,int ly,int x); void add(int u,int v) { next[++cnt]=head[u]; head[u]=cnt; to[cnt]=v; } void dfs1(int u,int v) { son[u]=-1; tol[u]=1; fa[u]=v; dep[u]=dep[v]+1; for (int i=head[u];i;i=next[i]) { int t=to[i]; if(t==v) continue ; dfs1(t,u); tol[u]+=tol[t]; if(son[u]==-1||(tol[t]>tol[son[u]])) son[u]=t; } } void dfs2(int u,int t) //t为链的顶端 { top[u]=t; dfn[u]=++cnt; rnk[cnt]=u; if(son[u]==-1) return ; dfs2(son[u],t); for (int i=head[u];i;i=next[i]) { if(to[i]!=fa[u]&&to[i]!=son[u]) //不为父亲和重儿子 dfs2(to[i],to[i]); //轻链顶端就是本身 } } void build(int l,int r,int x) { if(l==r) { treev[x]=value[rnk[l]]%p; return ; } int mid=l+r>>1; build(l,mid,x<<1); build(mid+1,r,x<<1|1); treev[x]=(treev[x<<1]+treev[x<<1|1])%p; } void update1(int l,int r,int lx,int ly,int x,int z) { if(lx<=l&&r<=ly) { treev[x]+=z*(r-l+1); lazy[x]+=z; return ; } int mid=l+r>>1; if(lazy[x]) pushdown(l,r,x); if(lx<=mid) update1(l,mid,lx,ly,x<<1,z); if(ly>mid) update1(mid+1,r,lx,ly,x<<1|1,z); treev[x]=(treev[x<<1]+treev[x<<1|1])%p; } void lca(int x,int y,int z) { while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) { update1(1,n,dfn[top[y]],dfn[y],1,z); y=fa[top[y]]; } else { update1(1,n,dfn[top[x]],dfn[x],1,z); x=fa[top[x]]; } } if(dep[x]<dep[y]) update1(1,n,dfn[x],dfn[y],1,z); else update1(1,n,dfn[y],dfn[x],1,z); } int sum(int x,int y) { int ans=0; while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) { ans+=query(1,n,dfn[top[y]],dfn[y],1); ans=ans%p; y=fa[top[y]]; } else { ans+=query(1,n,dfn[top[x]],dfn[x],1); ans=ans%p; x=fa[top[x]]; } } if(dep[x]<dep[y]) ans+=query(1,n,dfn[x],dfn[y],1); else ans+=query(1,n,dfn[y],dfn[x],1); return ans%p;; } void pushdown(int l,int r,int x) { lazy[x<<1]=(lazy[x<<1]+lazy[x])%p; lazy[x<<1|1]=(lazy[x<<1|1]+lazy[x])%p; treev[x<<1]=(treev[x<<1]+lazy[x]*((l+r>>1)-l+1))%p; treev[x<<1|1]=(treev[x<<1|1]+lazy[x]*(r-(l+r>>1)))%p; lazy[x]=0; } int query(int l,int r,int lx,int ly,int x) { if(lx<=l&&r<=ly) { // cout<<treev[x]<<endl; return treev[x]; } int mid=l+r>>1; int ans=0; if(lazy[x]) pushdown(l,r,x); if(lx<=mid) ans=(ans+query(l,mid,lx,ly,x<<1))%p; if(ly>mid) ans=(ans+query(mid+1,r,lx,ly,x<<1|1))%p; return ans; } int main() { cin>>n>>m>>r>>p; for (int i=1;i<=n;i++) { cin>>value[i]; } for (int i=0;i<n-1;i++) { int a,b; cin>>a>>b; add(a,b); add(b,a); } dfs1(r,r); cnt=0; dfs2(r,r); build(1,n,1); for (int i=0;i<m;i++) { int op; cin>>op; if(op==1) { int x,y,z; cin>>x>>y>>z; lca(x,y,z); } else if(op==2) { int x,y; cin>>x>>y; cout<<sum(x,y)<<endl; } else if(op==3) { int x,z; cin>>x>>z; // cout<<dfn[x]<<" "<<tol[x]<<endl; int y=dfn[x]+tol[x]-1; update1(1,n,dfn[x],y,1,z); } else{ int x; cin>>x; int y=dfn[x]+tol[x]-1; cout<<query(1,n,dfn[x],y,1)<<endl; } } }
    Processed: 0.081, SQL: 8