27pts，过了1,2,3点，悬关

Remedios @ 2023-07-16 23:25:26

by _XHY20180718_ @ 2023-07-16 23:37:46

@Remedios 忘记去摸了捏

by _XHY20180718_ @ 2023-07-16 23:44:17

@Remedios

多多取模，一般题不会卡这样的常。。。

#include<stdio.h>
#include<ctype.h>
#include<vector>
using namespace std;
const long long N=1e5+10,SN=4e5+10;
long long mo;
long long read(){
    long long res=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) res=(res<<3)+(res<<1)+c-48,c=getchar();
    return res*f;
}
struct ST{
    long long st[SN],lzm[SN];
    long long ls(long long p){ return p<<1; }
    long long rs(long long p){ return p<<1|1; }
    long long mid(long long s,long long t){ return s+((t-s)>>1); }
    void pushup(long long p){
        st[p]=st[ls(p)]+st[rs(p)];
        st[p]%=mo;
    }
    void add(long long s,long long t,long long p,long long k){
        st[p]+=(t-s+1)*k,lzm[p]+=k;
        st[p]%=mo,lzm[p]%=mo;
    }
    void pushdown(long long s,long long t,long long p){
        long long m=mid(s,t);
        add(s,m,ls(p),lzm[p]),add(m+1,t,rs(p),lzm[p]);
        lzm[p]=0;
    }
    void build(long long s,long long t,long long p,long long *od){
        if(s==t){
            st[p]=od[s]%mo;
            return ;
        }
        long long m=mid(s,t);
        build(s,m,ls(p),od),build(m+1,t,rs(p),od);
        pushup(p);
    }
    void sec_add(long long l,long long r,long long s,long long t,long long p,long long k){
        if(s>=l&&t<=r){
            add(s,t,p,k);
            return ;
        }
        long long m=mid(s,t); pushdown(s,t,p);
        if(m>=l) sec_add(l,r,s,m,ls(p),k);
        if(m<r) sec_add(l,r,m+1,t,rs(p),k);
        pushup(p);
    }
    long long sec_query(long long l,long long r,long long s,long long t,long long p){
        if(s>=l&&t<=r) return st[p];
        long long m=mid(s,t),sum=0; pushdown(s,t,p);
        if(m>=l) sum+=sec_query(l,r,s,m,ls(p)),sum%=mo;
        if(m<r) sum+=sec_query(l,r,m+1,t,rs(p)),sum%=mo;
        return sum;
    }
};
struct node{
    long long vl,fa,dep,size,hs,top,dfn,bot;
    node(){}
};
struct HD{
    long long n,rt,rnk[N],tot,df[N];
    node nd[N];
    vector<vector<long long>> g;
    ST da;
    long long tree_build(long long p,long long dep){
        nd[p].dep=dep,nd[p].size=1;
        for(auto i:g[p])if(!nd[i].dep){
            nd[p].size+=tree_build(i,dep+1);
            nd[i].fa=p;
            if(nd[i].size>nd[nd[p].hs].size)  nd[p].hs=i;
        }
        return nd[p].size;
    }
    long long tree_decomposition(long long p,long long top){
        nd[p].dfn=++tot,rnk[tot]=p,nd[p].top=top,df[tot]=nd[p].vl,nd[p].bot=p;

        if(nd[p].hs) nd[p].bot=nd[tree_decomposition(nd[p].hs,top)].dfn>nd[nd[p].bot].dfn?nd[nd[p].hs].bot:nd[p].bot;
        for(auto i:g[p]) if(!nd[i].dfn) nd[p].bot=nd[tree_decomposition(i,i)].dfn>nd[nd[p].bot].dfn?nd[i].bot:nd[p].bot;
        return nd[p].bot;
    }
    //HD(){}
    //HD(long long n1,long long r1,long long *od):n(n1),rt(r1){
    void build(long long n1,long long r1,long long *od){
        n=n1,rt=r1;
        g.resize(n+1);
        for(long long i=1;i<=n;i++) nd[i].vl=od[i];
        for(long long i=1;i<n;i++){
            long long u=read(),v=read();
            g[u].push_back(v);
            g[v].push_back(u);
        }
        tree_build(rt,1); tree_decomposition(rt,rt);
        da.build(1,n,1,df);
    }
    void path_add(long long s,long long t,long long k){
        while(nd[s].top!=nd[t].top){
            if(nd[nd[s].top].dep<nd[nd[t].top].dep) swap(s,t);
            da.sec_add(nd[nd[s].top].dfn,nd[s].dfn,1,n,1,k);
            s=nd[nd[s].top].fa;
        }
        long long ms=min(nd[s].dfn,nd[t].dfn),bs=nd[s].dfn+nd[t].dfn-ms;
        da.sec_add(ms,bs,1,n,1,k);
    }
    void subtree_add(long long p,long long k){ da.sec_add(nd[p].dfn,nd[nd[p].bot].dfn,1,n,1,k); }
    long long path_query(long long s,long long t){
        long long sum=0;
        while(nd[s].top!=nd[t].top){
            if(nd[nd[s].top].dep<nd[nd[t].top].dep) swap(s,t);
            (sum+=da.sec_query(nd[nd[s].top].dfn,nd[s].dfn,1,n,1))%=mo;
            s=nd[nd[s].top].fa;
        }
        long long ms=min(nd[s].dfn,nd[t].dfn),bs=nd[s].dfn+nd[t].dfn-ms;
        (sum+=da.sec_query(ms,bs,1,n,1))%=mo;
        return sum;
    }
    long long subtree_query(long long p){ return da.sec_query(nd[p].dfn,nd[nd[p].bot].dfn,1,n,1); }
} hd;

long long arr[N];
int main(){
    long long nn=read(),em=read(),ro=read(); mo=read();
    for(long long i=1;i<=nn;i++) arr[i]=read();
    hd.build(nn,ro,arr);
    while(em--){
        long long opt=read(),x,y,k;
        switch(opt){
            case 1:x=read(),y=read(),k=read(); hd.path_add(x,y,k);break;
            case 2:x=read(),y=read(); printf("%lld\n",hd.path_query(x,y));break;
            case 3:x=read(),k=read(); hd.subtree_add(x,k);break;
            case 4:x=read(); printf("%lld\n",hd.subtree_query(x));break;
        }
    }
    return 0;
}

能给个关注吗？

by Remedios @ 2023-07-16 23:46:00

@XHY20180718 谢谢你捏

by Remedios @ 2023-07-16 23:53:26

@XHY20180718 灌注了捏，太谢谢了哥