10分树剖，求义父调，悬赏一关注

上杉越 @ 2023-08-12 19:45:13

#include<bits/stdc++.h>
#define N 200086
#define mid ((l+r)>>1)
using namespace std;
int head[N],to[N*2],nex[N*2],tot;
int n,m,r,p;
void add(int u,int v){
    to[++tot]=v;
    nex[tot]=head[u];
    head[u]=tot;
}
int a[N],lazy[N],wt[N];
void build(int x,int l,int r){
    if(l==r){
        a[x]=wt[x];
        if(a[x]>p)a[x]%=p;
        return ;
    }
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    a[x]=(a[x<<1]+a[x<<1|1])%p;
}
void pushdown(int x,int len){
    lazy[x<<1]+=lazy[x];
    lazy[x<<1|1]+=lazy[x];
    a[x<<1]+=lazy[x]*(len-(len>>1));
    a[x<<1]%=p;
    a[x<<1|1]+=lazy[x]*(len>>1);
    a[x<<1|1]%=p;
    lazy[x]=0;
}
int res;
void query(int x,int l,int r,int L,int R){
    if(L<=l&&R>=r){
        res+=a[x];
        res%=p;
        return;
    }
    else{
        if(lazy[x])pushdown(x,r-l+1);
        if(L<=mid)query(x<<1,l,mid,L,R);
        if(R>mid)query(x<<1|1,mid+1,r,L,R);
    }
}
void update(int x,int k,int l,int r,int L,int R){
    if(L<=l&&R>=r){
        lazy[x]+=k;
        a[x]+=k*(r-l+1);
    }
    else{
        if(lazy[x])pushdown(x,r-l+1);
        if(L<=mid)update(x<<1,k,l,mid,L,R);
        if(R>mid)update(x<<1|1,k,mid+1,r,L,R);
        a[x]=(a[x<<1]+a[x<<1|1])%p;
    }
}
int dep[N],fa[N],sonsize[N],son[N];
void dfs1(int x,int f,int deep){
    fa[x]=f;
    dep[x]=deep;
    sonsize[x]=1;
    int maxson=-1;
    for(int i=head[x];i;i=nex[i]){
        if(to[i]==f)continue;
        dfs1(to[i],x,deep+1);
        sonsize[x]+=sonsize[to[i]];
        if(maxson<sonsize[to[i]]){
            maxson=sonsize[to[i]];
            son[x]=to[i];
        }
    }
}
int top[N],id[N],cnt,w[N];
void dfs2(int x,int topf){
    id[x]=++cnt;
    top[cnt]=topf;
    w[cnt]=wt[x];
    if(!son[x])return ;
    dfs2(son[x],topf);
    for(int i=head[x];i;i=nex[i]){
        if(to[i]==son[x]||to[i]==fa[x])continue;
        dfs2(to[i],to[i]);
    }
}
int qSon(int x){
    res=0;
    query(1,1,n,id[x],id[x]+sonsize[x]-1);
    return res;
}
void rSon(int x,int k){
    update(1,k,1,n,id[x],id[x]+sonsize[x]-1);
}
int range(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        res=0;
        query(1,1,n,id[top[x]],id[x]);
        ans+=res;
        ans%=p;
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    res=0;
    query(1,1,n,id[x],id[y]);
    ans+=res;
    ans%=p;
    return ans;
}
void up_date(int x,int y,int k){
    k%=p;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        update(1,k,1,n,id[top[x]],id[x]);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    update(1,k,1,n,id[x],id[y]);
}
int main(){
    cin>>n>>m>>r>>p;
    int x,y,z,B;
    for(int i=1;i<=n;i++)cin>>wt[i];
    for(int i=1;i<n;i++){
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    dfs1(r,0,1);
    dfs2(r,r);
    build(1,1,n);
    for(int i=1;i<=m;i++){
        cin>>B;
        if(B==1){
            cin>>x>>y>>z;
            up_date(x,y,z);
        }
        if(B==2){
            cin>>x>>y;
            cout<<range(x,y)<<"\n";
        }
        if(B==3){
            cin>>x>>y;
            rSon(x,y);
        }
        if(B==4){
            cin>>x;
            cout<<qSon(x)<<"\n";
        }
    }
    return 0;
}

by AAA404 @ 2023-08-12 19:53:22

@上杉越 build函数问题，要记录dfs序的逆操作rk，建树用rkx

by AAA404 @ 2023-08-12 19:54:42

按你代码里的操作也应该在建树时用w数组

by AAA404 @ 2023-08-12 19:55:58

而不是wt数组

by 上杉越 @ 2023-08-12 19:59:38

@AAA404 谢谢义父，但28

by 上杉越 @ 2023-08-12 20:00:57

@AAA404

#include<bits/stdc++.h>
#define N 200086
#define mid ((l+r)>>1)
using namespace std;
int head[N],to[N*2],nex[N*2],tot;
int top[N],id[N],cnt,w[N];
int n,m,r,p;
void add(int u,int v){
    to[++tot]=v;
    nex[tot]=head[u];
    head[u]=tot;
}
int a[N],lazy[N],wt[N];
void build(int x,int l,int r){
    if(l==r){
        a[x]=w[l];
        if(a[x]>p)a[x]%=p;
        return ;
    }
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    a[x]=(a[x<<1]+a[x<<1|1])%p;
}
void pushdown(int x,int len){
    lazy[x<<1]+=lazy[x];
    lazy[x<<1|1]+=lazy[x];
    a[x<<1]+=lazy[x]*(len-(len>>1));
    a[x<<1]%=p;
    a[x<<1|1]+=lazy[x]*(len>>1);
    a[x<<1|1]%=p;
    lazy[x]=0;
}
int res;
void query(int x,int l,int r,int L,int R){
    if(L<=l&&R>=r){
        res+=a[x];
        res%=p;
        return;
    }
    else{
        if(lazy[x])pushdown(x,r-l+1);
        if(L<=mid)query(x<<1,l,mid,L,R);
        if(R>mid)query(x<<1|1,mid+1,r,L,R);
    }
}
void update(int x,int k,int l,int r,int L,int R){
    if(L<=l&&R>=r){
        lazy[x]+=k;
        a[x]+=k*(r-l+1);
    }
    else{
        if(lazy[x])pushdown(x,r-l+1);
        if(L<=mid)update(x<<1,k,l,mid,L,R);
        if(R>mid)update(x<<1|1,k,mid+1,r,L,R);
        a[x]=(a[x<<1]+a[x<<1|1])%p;
    }
}
int dep[N],fa[N],sonsize[N],son[N];
void dfs1(int x,int f,int deep){
    fa[x]=f;
    dep[x]=deep;
    sonsize[x]=1;
    int maxson=-1;
    for(int i=head[x];i;i=nex[i]){
        if(to[i]==f)continue;
        dfs1(to[i],x,deep+1);
        sonsize[x]+=sonsize[to[i]];
        if(maxson<sonsize[to[i]]){
            maxson=sonsize[to[i]];
            son[x]=to[i];
        }
    }
}
void dfs2(int x,int topf){
    id[x]=++cnt;
    top[cnt]=topf;
    w[cnt]=wt[x];
    if(!son[x])return ;
    dfs2(son[x],topf);
    for(int i=head[x];i;i=nex[i]){
        if(to[i]==son[x]||to[i]==fa[x])continue;
        dfs2(to[i],to[i]);
    }
}
int qSon(int x){
    res=0;
    query(1,1,n,id[x],id[x]+sonsize[x]-1);
    return res;
}
void rSon(int x,int k){
    update(1,k,1,n,id[x],id[x]+sonsize[x]-1);
}
int range(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        res=0;
        query(1,1,n,id[top[x]],id[x]);
        ans+=res;
        ans%=p;
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    res=0;
    query(1,1,n,id[x],id[y]);
    ans+=res;
    ans%=p;
    return ans;
}
void up_date(int x,int y,int k){
    k%=p;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        update(1,k,1,n,id[top[x]],id[x]);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    update(1,k,1,n,id[x],id[y]);
}
int main(){
    cin>>n>>m>>r>>p;
    int x,y,z,B;
    for(int i=1;i<=n;i++)cin>>wt[i];
    for(int i=1;i<n;i++){
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    dfs1(r,0,1);
    dfs2(r,r);
    build(1,1,n);
    for(int i=1;i<=m;i++){
        cin>>B;
        if(B==1){
            cin>>x>>y>>z;
            up_date(x,y,z);
        }
        if(B==2){
            cin>>x>>y;
            cout<<range(x,y)<<"\n";
        }
        if(B==3){
            cin>>x>>y;
            rSon(x,y);
        }
        if(B==4){
            cin>>x;
            cout<<qSon(x)<<"\n";
        }
    }
    return 0;
}

by AAA404 @ 2023-08-12 20:01:27

@上杉越 az，代码发出来，我没写这题看不了

by AAA404 @ 2023-08-12 20:02:50

dfs2里的top不是cnt是x

by 上杉越 @ 2023-08-12 20:04:18

@AAA404 谢谢大佬，73了

by 上杉越 @ 2023-08-12 20:04:53

@AAA404

#include<bits/stdc++.h>
#define N 200086
#define mid ((l+r)>>1)
using namespace std;
int head[N],to[N*2],nex[N*2],tot;
int top[N],id[N],cnt,w[N];
int n,m,r,p;
void add(int u,int v){
    to[++tot]=v;
    nex[tot]=head[u];
    head[u]=tot;
}
int a[N],lazy[N],wt[N];
void build(int x,int l,int r){
    if(l==r){
        a[x]=w[l];
        if(a[x]>p)a[x]%=p;
        return ;
    }
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    a[x]=(a[x<<1]+a[x<<1|1])%p;
}
void pushdown(int x,int len){
    lazy[x<<1]+=lazy[x];
    lazy[x<<1|1]+=lazy[x];
    a[x<<1]+=lazy[x]*(len-(len>>1));
    a[x<<1]%=p;
    a[x<<1|1]+=lazy[x]*(len>>1);
    a[x<<1|1]%=p;
    lazy[x]=0;
}
int res;
void query(int x,int l,int r,int L,int R){
    if(L<=l&&R>=r){
        res+=a[x];
        res%=p;
        return;
    }
    else{
        if(lazy[x])pushdown(x,r-l+1);
        if(L<=mid)query(x<<1,l,mid,L,R);
        if(R>mid)query(x<<1|1,mid+1,r,L,R);
    }
}
void update(int x,int k,int l,int r,int L,int R){
    if(L<=l&&R>=r){
        lazy[x]+=k;
        a[x]+=k*(r-l+1);
    }
    else{
        if(lazy[x])pushdown(x,r-l+1);
        if(L<=mid)update(x<<1,k,l,mid,L,R);
        if(R>mid)update(x<<1|1,k,mid+1,r,L,R);
        a[x]=(a[x<<1]+a[x<<1|1])%p;
    }
}
int dep[N],fa[N],sonsize[N],son[N];
void dfs1(int x,int f,int deep){
    fa[x]=f;
    dep[x]=deep;
    sonsize[x]=1;
    int maxson=-1;
    for(int i=head[x];i;i=nex[i]){
        if(to[i]==f)continue;
        dfs1(to[i],x,deep+1);
        sonsize[x]+=sonsize[to[i]];
        if(maxson<sonsize[to[i]]){
            maxson=sonsize[to[i]];
            son[x]=to[i];
        }
    }
}
void dfs2(int x,int topf){
    id[x]=++cnt;
    top[x]=topf;
    w[cnt]=wt[x];
    if(!son[x])return ;
    dfs2(son[x],topf);
    for(int i=head[x];i;i=nex[i]){
        if(to[i]==son[x]||to[i]==fa[x])continue;
        dfs2(to[i],to[i]);
    }
}
int qSon(int x){
    res=0;
    query(1,1,n,id[x],id[x]+sonsize[x]-1);
    return res;
}
void rSon(int x,int k){
    update(1,k,1,n,id[x],id[x]+sonsize[x]-1);
}
int range(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        res=0;
        query(1,1,n,id[top[x]],id[x]);
        ans+=res;
        ans%=p;
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    res=0;
    query(1,1,n,id[x],id[y]);
    ans+=res;
    ans%=p;
    return ans;
}
void up_date(int x,int y,int k){
    k%=p;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        update(1,k,1,n,id[top[x]],id[x]);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    update(1,k,1,n,id[x],id[y]);
}
int main(){
    cin>>n>>m>>r>>p;
    int x,y,z,B;
    for(int i=1;i<=n;i++)cin>>wt[i];
    for(int i=1;i<n;i++){
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    dfs1(r,0,1);
    dfs2(r,r);
    build(1,1,n);
    for(int i=1;i<=m;i++){
        cin>>B;
        if(B==1){
            cin>>x>>y>>z;
            up_date(x,y,z);
        }
        if(B==2){
            cin>>x>>y;
            cout<<range(x,y)<<"\n";
        }
        if(B==3){
            cin>>x>>y;
            rSon(x,y);
        }
        if(B==4){
            cin>>x;
            cout<<qSon(x)<<"\n";
        }
    }
    return 0;
}