蒟蒻树链剖分模板WA求调

liaoz123 @ 2023-01-11 09:35:37

by liaoz123 @ 2023-01-11 09:36:00

代码如下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
struct node{
    int nxt,to;
    ll dis;
}e[N];
//id表示dfs序，top表示链顶，siz表示子树大小，son表示重儿子编号，f表示父亲编号
//num表示边数，ww表示原节点值，w表示线段树上的值，s为线段树 
int num,head[N],top[N],f[N],dep[N],siz[N],id[N],cnt,son[N];
ll s[N<<2],tag[N<<2],mod,ww[N],w[N];
void add(int x,int y){
    e[++num].to=y;
    e[num].nxt=head[x];
    head[x]=num;
}
int n,m,r;//树链剖分部分 
void dfs1(int u,int fa){
    f[u]=fa;
    dep[u]=dep[fa]+1;
    siz[u]=1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa)continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(!son[u]||siz[v]>siz[son[u]])
        son[u]=v;
    }
}
void dfs2(int u,int val){
    top[u]=val;
    id[u]=++cnt;
    w[cnt]=ww[u];
    if(!son[u])return;
    dfs2(son[u],val);
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v!=son[u]&&v!=f[u])dfs2(v,v);
    }
}
void pushup(int k){//合并 
    s[k]=(s[k*2]+s[k*2+1])%mod;
}
void addtag(int k,int l,int r,ll val){//懒标记下传 
    s[k]=(s[k]+ll(r-l+1)*val)%mod;
    tag[k]+=val;tag[k]%mod;
}
void pushdown(int k,int l,int r){ 
    int mid=(l+r)>>1;
    addtag(k*2,l,mid,tag[k]);
    addtag(k*2+1,mid+1,r,tag[k]);
    tag[k]=0;
}
void build(int k,int l,int r){//建树 
    if(l==r){
        s[k]=w[l];
        return;
    }
    int mid=(l+r)>>1;
    build(k*2,l,mid);
    build(k*2+1,mid+1,r);
    pushup(k);
}
ll query(int k,int l,int r,int x,int y){//线段树询问 
    if(l>y||r<x)return 0;
    if(l>=x&&r<=y)return s[k]%mod;
    int mid=(l+r)>>1;
    pushdown(k,l,r);
    return (query(k*2,l,mid,x,y)+query(k*2+1,mid+1,r,x,y))%mod;
}
void change(int k,int l,int r,int x,int y,ll val){//线段树改变 
    if(l>y||r<x)return;
    if(l>=x&&r<=y){
        addtag(k,l,r,val);
        return;
    }
    int mid=(l+r)>>1;
    pushdown(k,l,r);
    change(k*2,l,mid,x,y,val);
    change(k*2+1,mid+1,r,x,y,val);
    pushup(k);
}
void update_range(int x,int y,ll val){//路径add 
    ll ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        change(1,1,n,id[top[x]],id[x],val);
        x=f[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    change(1,1,n,id[x],id[y],val);
}
ll query_range(int x,int y){//路径求和 
    ll ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        ans=(ans+query(1,1,n,id[x],id[top[x]]))%mod;
        x=f[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    ans=(ans+query(1,1,n,id[x],id[y]))%mod;
}
void update_tree(int x,ll val){change(1,1,n,id[x],id[x]+siz[x]-1,val);}//子树改变 
ll query_tree(int x){return query(1,1,n,id[x],id[x]+siz[x]-1);}//子树求和 
int main(){
    //freopen("P3384_1.in","r",stdin);
    scanf("%d%d%d%lld",&n,&m,&r,&mod);
    for(int i=1;i<=n;i++)scanf("%lld",&ww[i]);
    for(int i=1,x,y;i<n;i++){
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    dfs1(r,0);
    dfs2(r,r);
    build(1,1,n);
    while(m--){
        int op,x;ll y,z;
        scanf("%d",&op);
        switch(op){
            case 1:scanf("%d%d%lld",&x,&y,&z);update_range(x,y,z);break;
            case 2:scanf("%d%d",&x,&y);printf("%lld\n",query_range(x,y));break;
            case 3:scanf("%d%lld",&x,&y);update_tree(x,y);break;
            case 4:scanf("%d",&x);printf("%lld\n",query_tree(x));break;
        }
    }
    return 0;
}

by liaoz123 @ 2023-01-11 10:08:48

已AC，谢谢大家