27pt

include13_fAKe @ 2024-07-11 11:56:37

#include<bits/stdc++.h>
#define int long long 
using namespace std;

const int maxn=114514;
struct Edge{
    int to;
    int nxt;
}edge[2*maxn];
struct segment_tree{
//  int id;
    int l;
    int r;
    int num;
    int tag;
}tree[4*maxn];
int head[maxn];
int idx;

int N,M,R,P;
int st[maxn];
void add(int u,int v){
    ++idx;
    edge[idx].nxt=head[u];
    edge[idx].to=v;
    head[u]=idx;
}
int fa[maxn];   //父亲
int son[maxn];  //重儿子
int siz[maxn];  //子树大小 
int top[maxn];  //顶节点 
int dep[maxn]; 

int stamp; 
int dfn[maxn];  //dfn 序 
int rank_[maxn];    //线段树上第 i 个节点表示实际上的第 rank_[i] 个节点 
void dfs1(int u,int fa_){
    int max_son=0;
    fa[u]=fa_;
    siz[u]=1;
    if(fa_!=-1) dep[u]=dep[fa_]+1;
    else    dep[u]=1;
    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].to;
        if(v==fa[u])    continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>max_son){
            max_son=siz[v];
            son[u]=v;
        }
    }
} 
void dfs2(int u,int top_){
    stamp++;
    dfn[u]=stamp;
    top[u]=top_;
    if(son[u])  dfs2(son[u],top_);
    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].to;
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}
void pushup(int id){
    tree[id].num=tree[id*2].num+tree[id*2+1].num;
    tree[id].num%=P;
}
void pushdown(int id){
    tree[id*2].tag+=tree[id].tag;
    tree[id*2].num+=(tree[id*2].r-tree[id*2].l+1)*tree[id].tag;
    tree[id*2+1].tag+=tree[id].tag;
    tree[id*2+1].num+=(tree[id*2+1].r-tree[id*2+1].l+1)*tree[id].tag;
    tree[id].tag=0;
}
void build(int id,int l,int r){
//  tree[id].id=id;
    tree[id].l=l;
    tree[id].r=r;
    if(l==r){
        tree[id].num=st[rank_[l]];
//      cout<<tree[id].num<<' ';
        return;
    }
    int mid=l+r>>1;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    pushup(id);
}
bool f;
void modify(int id,int l,int r,int num){
//  cout<<id<<' '<<l<<' '<<r<<' '<<num<<endl;
    int l1=tree[id].l;
    int r1=tree[id].r;
    if(l1!=r1)  pushdown(id);
    if(l==l1&&r==r1){
//      cout<<l<<' '<<r<<' '<<num<<endl;
        tree[id].tag+=num;
        tree[id].num+=(tree[id].r-tree[id].l+1)*num;
        return;
    }
    if(r<l1||l>r1)  return;
    int mid=l1+r1>>1;
    if(l<=mid)  modify(id*2,l,min(mid,r),num);
    if(r>mid)   modify(id*2+1,max(mid+1,l),r,num);
    pushup(id);
}
int query(int id,int l,int r){
    int ans=0;
    int l1=tree[id].l;
    int r1=tree[id].r;
    if(l1!=r1)  pushdown(id);
    if(l==l1&&r==r1){
//      cout<<l<<' '<<r<<' '<<tree[id].num<<endl;
        return tree[id].num;
    }
    if(r<l1||l>r1)  return 0;
    int mid=l1+r1>>1;
    if(l<=mid)  ans+=query(id*2,l,min(mid,r));
    if(r>mid)   ans+=query(id*2+1,max(mid+1,l),r);
    pushup(id);
    return ans;
}
void modify1(int x,int y,int z){
//  cout<<dfn[x]<<' '<<dfn[y]<<endl<<endl<<endl<<endl<<endl<<endl<<endl<<endl;
    while(top[x]!=top[y]){
        f=true;
//      cout<<x<<' '<<y<<endl;
        int x_=top[x];
        int y_=top[y];
        if(dep[x_]<dep[y_]){
            swap(x,y);
            swap(x_,y_);
        }
//      cout<<dfn[x_]<<' '<<dfn[x]<<endl;
        modify(1,dfn[x_],dfn[x],z);
        x=fa[x_];
    }
    if(dep[x]>dep[y]){
        swap(x,y);
    }
    f=true;
//  cout<<dfn[x]<<' '<<dfn[y]<<endl;
    modify(1,dfn[x],dfn[y],z);
    return;
} 
int query1(int x,int y){
//  cout<<dfn[x]<<' '<<dfn[y]<<endl<<endl<<endl<<endl<<endl<<endl<<endl<<endl;
    int ans=0;
    while(top[x]!=top[y]){
        int x_=top[x];
        int y_=top[y];
        if(dep[x_]<dep[y_]){
            swap(x,y);
            swap(x_,y_);
        }
        ans+=query(1,dfn[x_],dfn[x]);
        ans%=P;
//      cout<<ans<<endl;
        x=fa[x_];
    }
    if(dep[x]>dep[y]){
        swap(x,y);
    }
    f=true;
    ans+=query(1,dfn[x],dfn[y]);
    ans%=P; 
    return ans;
}
void modify2(int x,int z){
    int x_=dfn[x]+siz[x]-1;
//  cout<<dfn[x]<<' '<<x_<<endl;
    modify(1,dfn[x],x_,z);
}
int query2(int x){
    int x_=dfn[x]+siz[x]-1;
    return query(1,dfn[x],x_);
}
signed main(){
    scanf("%lld%lld%lld%lld",&N,&M,&R,&P);
    for(int i=1;i<=N;i++){
        scanf("%lld",&st[i]);
    }
    for(int i=1;i<N;i++){
        int u,v;
        scanf("%lld%lld",&u,&v);
        add(u,v);
        add(v,u);
    }
    dfs1(R,-1);
    dfs2(R,R);
    for(int i=1;i<=N;i++){
//      cout<<dfn[i]<<' '<<top[i]<<endl;
        rank_[dfn[i]]=i;
    }
//  for(int i=1;i<=N;i++){
//      cout<<rank_[i]<<endl;
//  }
//  for(int i=1;i<=N;i++){
//      cout<<
//  }
    build(1,1,N);
//  cout<<endl;
    while(M--){
        int op;
        scanf("%lld",&op);
        switch(op){
            case 1:{
                int x,y,z;
                scanf("%lld%lld%lld",&x,&y,&z);
                modify1(x,y,z);
//              cout<<endl;
                break;
            }
            case 2:{
                int x,y;
                scanf("%lld%lld",&x,&y);
                printf("%lld\n",query1(x,y));
                break;
            }
            case 3:{
                int x,z;
                scanf("%lld%lld",&x,&z);
                modify2(x,z);
                break;
            }
            case 4:{
                int x;
                scanf("%lld",&x);
                printf("%lld\n",query2(x));
                break;
            }
        }
    }
    return 0;
}//来自星辰大海 向往美好未来 

by Mugino_Shizuri @ 2024-07-11 14:36:40

@include13_fAKe

取模漏完了。

AC_code

#include<bits/stdc++.h>
#define int long long 
using namespace std;

const int maxn=114514;
struct Edge{
    int to;
    int nxt;
}edge[2*maxn];
struct segment_tree{
//  int id;
    int l;
    int r;
    int num;
    int tag;
}tree[4*maxn];
int head[maxn];
int idx;

int N,M,R,P;
int st[maxn];
void add(int u,int v){
    ++idx;
    edge[idx].nxt=head[u];
    edge[idx].to=v;
    head[u]=idx;
}
int fa[maxn];   //父亲
int son[maxn];  //重儿子
int siz[maxn];  //子树大小 
int top[maxn];  //顶节点 
int dep[maxn]; 

int stamp; 
int dfn[maxn];  //dfn 序 
int rank_[maxn];    //线段树上第 i 个节点表示实际上的第 rank_[i] 个节点 
void dfs1(int u,int fa_){
    int max_son=0;
    fa[u]=fa_;
    siz[u]=1;
    if(fa_!=-1) dep[u]=dep[fa_]+1;
    else    dep[u]=1;
    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].to;
        if(v==fa[u])    continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>max_son){
            max_son=siz[v];
            son[u]=v;
        }
    }
} 
void dfs2(int u,int top_){
    stamp++;
    dfn[u]=stamp;
    top[u]=top_;
    if(son[u])  dfs2(son[u],top_);
    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].to;
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}
void pushup(int id){
    tree[id].num=tree[id*2].num+tree[id*2+1].num;
    tree[id].num%=P;
}
void pushdown(int id){
    tree[id*2].tag+=tree[id].tag;
    tree[id*2].num+=(tree[id*2].r-tree[id*2].l+1)*tree[id].tag;
    tree[id*2+1].tag+=tree[id].tag;
    tree[id*2+1].num+=(tree[id*2+1].r-tree[id*2+1].l+1)*tree[id].tag;
    tree[id*2].tag%=P;
    tree[id*2].num%=P;
    tree[id*2+1].tag%=P;
    tree[id*2+1].num%=P;
    tree[id].tag=0;
}
void build(int id,int l,int r){
//  tree[id].id=id;
    tree[id].l=l;
    tree[id].r=r;
    if(l==r){
        tree[id].num=st[rank_[l]];
//      cout<<tree[id].num<<' ';
        return;
    }
    int mid=l+r>>1;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    pushup(id);
}
bool f;
void modify(int id,int l,int r,int num){
//  cout<<id<<' '<<l<<' '<<r<<' '<<num<<endl;
    int l1=tree[id].l;
    int r1=tree[id].r;
    if(l1!=r1)  pushdown(id);
    if(l==l1&&r==r1){
//      cout<<l<<' '<<r<<' '<<num<<endl;
        tree[id].tag+=num;
        tree[id].num+=(tree[id].r-tree[id].l+1)*num;
        tree[id].tag%=P;
        tree[id].num%=P;
        return;
    }
    if(r<l1||l>r1)  return;
    int mid=l1+r1>>1;
    if(l<=mid)  modify(id*2,l,min(mid,r),num);
    if(r>mid)   modify(id*2+1,max(mid+1,l),r,num);
    pushup(id);
}
int query(int id,int l,int r){
    int ans=0;
    int l1=tree[id].l;
    int r1=tree[id].r;
    if(l1!=r1)  pushdown(id);
    if(l==l1&&r==r1){
//      cout<<l<<' '<<r<<' '<<tree[id].num<<endl;
        return tree[id].num;
    }
    if(r<l1||l>r1)  return 0;
    int mid=l1+r1>>1;
    if(l<=mid)  ans+=query(id*2,l,min(mid,r));
    if(r>mid)   ans+=query(id*2+1,max(mid+1,l),r);
    pushup(id);
    return ans%P;
}
void modify1(int x,int y,int z){
//  cout<<dfn[x]<<' '<<dfn[y]<<endl<<endl<<endl<<endl<<endl<<endl<<endl<<endl;
    while(top[x]!=top[y]){
        f=true;
//      cout<<x<<' '<<y<<endl;
        int x_=top[x];
        int y_=top[y];
        if(dep[x_]<dep[y_]){
            swap(x,y);
            swap(x_,y_);
        }
//      cout<<dfn[x_]<<' '<<dfn[x]<<endl;
        modify(1,dfn[x_],dfn[x],z);
        x=fa[x_];
    }
    if(dep[x]>dep[y]){
        swap(x,y);
    }
    f=true;
//  cout<<dfn[x]<<' '<<dfn[y]<<endl;
    modify(1,dfn[x],dfn[y],z);
    return;
} 
int query1(int x,int y){
//  cout<<dfn[x]<<' '<<dfn[y]<<endl<<endl<<endl<<endl<<endl<<endl<<endl<<endl;
    int ans=0;
    while(top[x]!=top[y]){
        int x_=top[x];
        int y_=top[y];
        if(dep[x_]<dep[y_]){
            swap(x,y);
            swap(x_,y_);
        }
        ans+=query(1,dfn[x_],dfn[x]);
        ans%=P;
//      cout<<ans<<endl;
        x=fa[x_];
    }
    if(dep[x]>dep[y]){
        swap(x,y);
    }
    f=true;
    ans+=query(1,dfn[x],dfn[y]);
    ans%=P; 
    return ans;
}
void modify2(int x,int z){
    int x_=dfn[x]+siz[x]-1;
//  cout<<dfn[x]<<' '<<x_<<endl;
    modify(1,dfn[x],x_,z);
}
int query2(int x){
    int x_=dfn[x]+siz[x]-1;
    return query(1,dfn[x],x_);
}
signed main(){
    scanf("%lld%lld%lld%lld",&N,&M,&R,&P);
    for(int i=1;i<=N;i++){
        scanf("%lld",&st[i]);
    }
    for(int i=1;i<N;i++){
        int u,v;
        scanf("%lld%lld",&u,&v);
        add(u,v);
        add(v,u);
    }
    dfs1(R,-1);
    dfs2(R,R);
    for(int i=1;i<=N;i++){
//      cout<<dfn[i]<<' '<<top[i]<<endl;
        rank_[dfn[i]]=i;
    }
//  for(int i=1;i<=N;i++){
//      cout<<rank_[i]<<endl;
//  }
//  for(int i=1;i<=N;i++){
//      cout<<
//  }
    build(1,1,N);
//  cout<<endl;
    while(M--){
        int op;
        scanf("%lld",&op);
        switch(op){
            case 1:{
                int x,y,z;
                scanf("%lld%lld%lld",&x,&y,&z);
                modify1(x,y,z);
//              cout<<endl;
                break;
            }
            case 2:{
                int x,y;
                scanf("%lld%lld",&x,&y);
                printf("%lld\n",query1(x,y)%P);
                break;
            }
            case 3:{
                int x,z;
                scanf("%lld%lld",&x,&z);
                modify2(x,z);
                break;
            }
            case 4:{
                int x;
                scanf("%lld",&x);
                printf("%lld\n",query2(x)%P);
                break;
            }
        }
    }
    return 0;
}//来自星辰大海 向往美好未来