Mn Zn只ac 1,3 求调

XX学校XX学校计算机机房倒闭了

王八蛋王八蛋XX老师不调代码不调代码

带着他的笔记本跑了

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=400005;
int n,m,ss,mod;
int num[N];
int dfn[N],rev[N],sz[N],top[N],dep[N],faa[N];
vector<int>mp[N];
struct node{
    int le;
    int ri;
    int sum;
    int lz;
}tree[N*4];
void pushup(int rt){
    tree[rt].sum=tree[rt*2].sum+tree[rt*2+1].sum;
    tree[rt].sum%=mod;
}
void pushdown(int rt){
    if(tree[rt].lz!=0){
        tree[rt*2].lz+=tree[rt].lz;
        tree[rt*2+1].lz+=tree[rt].lz;
        tree[rt*2].lz%=mod;
        tree[rt*2+1].lz%=mod;

        int mid=(tree[rt].le+tree[rt].ri)/2;
        tree[rt*2].sum+=tree[rt].lz*(mid-tree[rt*2].le+1);//左右分别求和加起来
        tree[rt*2+1].sum+=tree[rt].lz*(tree[rt*2+1].ri-mid);
        tree[rt*2].sum%=mod;
        tree[rt*2+1].sum%=mod;
        tree[rt].lz=0;
    }
}
void build(int rt,int l,int r){
    tree[rt].le=l;
    tree[rt].ri=r;
    tree[rt].lz=0;
    int mid=(l+r)/2;
    if(l==r){
        tree[rt].sum=num[rev[l]]; 
        return ;
    }
    build(rt*2,l,mid);
    build(rt*2+1,mid+1,r);
    pushup(rt);

}
void updata(int rt,int cl,int cr,int val){
    if(tree[rt].le>=cl&&tree[rt].ri<=cr){
        tree[rt].sum+=(tree[rt].ri-tree[rt].ri+1)*val;
        tree[rt].sum%=mod;
        tree[rt].lz+=val;
        return;
    }
    pushdown(rt);
    if(tree[rt*2].ri>=cl)
        updata(rt*2,cl,cr,val);
    if(tree[rt*2+1].le<=cr)
        updata(rt*2+1,cl,cr,val);
    pushup(rt);
}
int query(int rt,int l,int r){
    if(tree[rt].le>=l && tree[rt].ri<=r)
        return tree[rt].sum%mod;
    pushdown(rt);
    int s=0;
    if(tree[rt*2].ri>=l)  s+=query(rt*2,l,r);
    if(tree[rt*2+1].le<=r)  s+=query(rt*2+1,l,r);
    return s%mod;
}
//------------
int st=0;
void dfs1(int x,int fa){
    sz[x]=1;
    int ma=-1;
    faa[x]=fa;
    dep[x]=dep[fa]+1;
    for(int i=0;i<mp[x].size();i++){
        int to=mp[x][i];
        if(to==fa){
            continue;
        }
        dfs1(to,x);
        sz[x]+=sz[to];
        if(mp[x][0]==fa||ma<sz[to]){
            ma=sz[to];
            swap(mp[x][0],mp[x][i]);
        }
    }
}
void dfs2(int x,int fa,int ttop){
    st++;
    dfn[x]=st;
    rev[st]=x;
    top[x]=ttop;
    if(mp[x][0]==fa){//没有儿子 
        return;
    }
    dfs2(mp[x][0],x,ttop);
    for(int i=1;i<mp[x].size();i++){
        int to=mp[x][i];
        if(to==fa){
            continue;
        }
        dfs2(to,x,to);
    }
}
int qrange(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){//当两个点不在同一条链上 
        if(dep[top[x]]<dep[top[y]])swap(x,y);//把x点改为所在链顶端的深度更深的那个点
        int res=query(1,dfn[top[x]],dfn[x]);//ans加上x点到x所在链顶端 这一段区间的点权和
        ans+=res;
        ans%=mod;//按题意取模 
        x=faa[top[x]];//把x跳到x所在链顶端的那个点的上面一个点
    }
    //直到两个点处于一条链上
    if(dep[x]>dep[y])swap(x,y);//把x点深度更深的那个点
    int res=query(1,dfn[x],dfn[y]);//这时再加上此时两个点的区间和即可
    ans+=res;
    return ans%mod;
}
void qup(int x,int y,int z){
    while(top[x]!=top[y]){//当两个点不在同一条链上 
        if(dep[top[x]]<dep[top[y]])swap(x,y);//把x点改为所在链顶端的深度更深的那个点
        updata(1,dfn[top[x]],dfn[x],z);//ans加上x点到x所在链顶端 这一段区间的点权和
        x=faa[top[x]];//把x跳到x所在链顶端的那个点的上面一个点
    }
    //直到两个点处于一条链上
    if(dep[x]>dep[y])swap(x,y);//把x点深度更浅的那个点
    updata(1,dfn[x],dfn[y],z);
}
int treerange(int x){
    return query(1,dfn[x],dfn[x]+sz[x]-1);
}
void treeup(int x,int z){
    updata(1,dfn[x],dfn[x]+sz[x]-1,z); 
}
signed main(){
    ios::sync_with_stdio(false);
    cin >> n >>m >> ss >> mod;
    for(int i=1;i<=n;i++){
        cin >> num[i];
        num[i]%=mod;
    }
    for(int i=1;i<=n-1;i++){
        int a,b;
        cin >> a >> b;
        mp[a].push_back(b);
        mp[b].push_back(a);
    }
    dep[ss]=1;
    dfs1(ss,0);
    dfs2(ss,ss,ss);
    build(1,1,n);
    while(m--){
        int op;
        cin >> op;
        if(op==1){
            int x,y,z;
            cin >> x >> y >> z;
            qup(x,y,z);
        }
        else if(op==2){
            int x,y;
            cin >> x >> y;
            cout<<qrange(x,y)<<endl;
        }
        else if(op==3){
            int x,z;
            cin >> x >> z;
            treeup(x,z);
        }
        else{
            int x;
            cin >> x;
            cout<<treerange(x)<<endl;
        }
    }
}