简单板子求救(WA73

P3384,救一下孩子把,取模炸了没调出来题目

#include<bits/stdc++.h>
#define int long long
const int N=114514;
using namespace std;
int head[N],cnt;
int dfn;
int n,m,rt,mod,a[N],w[N],tree[N*4],lazy[N];
int ls(int p){return p<<1;} 
int rs(int p){return (p<<1)+1;}
struct edge{
    int next,to;
}e[N];
void add_edge(int u,int v){
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
struct node{
    int size,top,son,dep,fa,id,rk;
    node(){
        memset(this,0,sizeof(node));
    }
}p[N];
void dfs(int u,int fa){
    p[u].fa=fa;//结点的父亲
    p[u].size=1;//子树的结点个数
    p[u].dep=p[fa].dep+1;//结点深度
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u);
        p[u].size+=p[v].size;
        if(p[u].son==0|p[v].size>p[p[u].son].size){
            p[u].son=v;//重儿子
        }
    }
}
void dfs2(int u,int t){
    p[u].id=++dfn;
    p[u].top=t;
    if(!p[u].son) return;
    dfs2(p[u].son,t);//先遍历重儿子
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to; 
        if(v==p[u].fa|v==p[u].son) continue;
        dfs2(v,v);
    }   
}
void pushup(int p){
    tree[p]=(tree[ls(p)]+tree[rs(p)])%mod;
}
void build(int p,int pl,int pr){
    if(pl==pr){tree[p]=w[pl];return;}
    int mid=(pl+pr)>>1;
    build(ls(p),pl,mid);
    build(rs(p),mid+1,pr);
    pushup(p);
}
void add(int p,int pl,int pr,int k){
    lazy[p]=(lazy[p]+k);
    tree[p]=(tree[p]+(pr-pl+1)*k);
}
void pushdown(int p,int pl,int pr){
    if(lazy[p]){
        int mid=(pl+pr)>>1;
        add(ls(p),pl,mid,lazy[p]);
        add(rs(p),mid+1,pr,lazy[p]);
        lazy[p]=0;
    }
}   
void update(int p,int pl,int pr,int l,int r,int k){
    if(l<=pl&&pr<=r){
        add(p,pl,pr,k);
        return;
    }
    pushdown(p,pl,pr);
    int mid=(pl+pr)>>1;
    if(l<=mid) update(ls(p),pl,mid,l,r,k);
    if(mid<r) update(rs(p),mid+1,pr,l,r,k);
    pushup(p);
}
int query(int p,int pl,int pr,int l,int r){
        if(l<=pl&&pr<=r){return tree[p]%mod;}
        int res=0,mid=(pl+pr)>>1;
        pushdown(p,pl,pr);
        if(l<=mid) res=(res+query(ls(p),pl,mid,l,r))%mod;
        if(mid<r) res=(res+query(rs(p),mid+1,pr,l,r))%mod;
        return res%mod;
}
void upd_c(int x,int y,int k){
    while(p[x].top!=p[y].top){//不在同一个链上
        if(p[p[x].top].dep<p[p[y].top].dep){swap(x,y);}//让链顶深度深
        update(1,1,n,p[p[x].top].id,p[x].id,k);
        x=p[p[x].top].fa;
    }
    if(p[x].dep<p[y].dep){swap(x,y);}
    update(1,1,n,p[y].id,p[x].id,k);
}
int que_c(int x,int y){
    int res=0;
    while(p[x].top!=p[y].top){
        if(p[p[x].top].dep<p[p[y].top].dep){swap(x,y);}
        res=(res+query(1,1,n,p[p[x].top].id,p[x].id))%mod;
        x=p[p[x].top].fa;
    }
    if(p[x].dep<p[y].dep) {swap(x,y);}
    res=(res+query(1,1,n,p[y].id,p[x].id))%mod;
    return res%mod;
}
void upd_r(int x,int k){
    update(1,1,n,p[x].id,p[x].id+p[x].size-1,k);
}
int que_r(int x){
    return query(1,1,n,p[x].id,p[x].id+p[x].size-1)%mod;
}
signed main(){
    cin>>n>>m>>rt>>mod;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n-1;i++){
        int x,y;
        cin>>x>>y;
        add_edge(x,y);
        add_edge(y,x);
    }
    dfs(rt,rt);
    dfs2(rt,rt);
    for(int i=1;i<=n;i++){
        w[p[i].id]=a[i];
    }
    build(1,1,n);
    while(m--){
        int op,x,y,z;
        cin>>op;
        if(op==1){
            cin>>x>>y>>z;
            upd_c(x,y,z);
        }
        else if(op==2){
            cin>>x>>y;
            cout<<que_c(x,y)<<endl;
        }
        else if(op==3){
            cin>>x>>z;
            upd_r(x,z);
        }
        else{
            cin>>x;
            cout<<que_r(x)<<endl;
        }
    }
    //system("pause");
    return 0;

}
2 个赞

救一下吧

1 个赞

挂两天了,没人看一下吗?

1 个赞

洛谷看题解…

这是板子看什么题解,细节问题看不出来吗

因为建的是双向边,所以得开两倍空间,懒标记也开小了,此贴结