悬关-求调！

i__ak_io @ 2024-07-16 09:54:12

#include <iostream>
#include <cstdio>

using namespace std;

#define lnode(x) x<<1
#define rnode(x) x<<1|1
#define lld long long
const int N=1e5+5;

struct Tree {int val,tag,lid,rid;} tree[N<<2];
struct Edge {int val,beg,nex;} edge[N<<1];
struct Point {int son,father,siz,deep,top,id;} point[N<<2];

int n,m,r,p,op;
int tot=0,index=0;
int in[N],in_new[N];

void addedge (int x,int y) {
    edge[++tot].val=y;
    edge[tot].nex=edge[x].beg;
    edge[x].beg=tot;
}

void dfs_first (int node,int fa) {
    point[node].deep=point[fa].deep+1;
    point[node].father=fa;
    point[node].siz=1;
    for (int i=edge[node].beg;i;i=edge[i].nex) {
        int k=edge[i].val;
        if (k==fa) continue;
//      point[k].father=node;
        dfs_first(k,node);
        point[node].siz+=point[k].siz;
        if (point[point[node].son].siz<point[k].siz) point[node].son=k;
    }
}

void dfs_second (int node,int top) {
    point[node].id=++index;
    in_new[index]=in[node];
    point[node].top=top;
    if (!point[node].son) return ;
    dfs_second(point[node].son,top);
    for (int i=edge[node].beg;i;i=edge[node].nex) {
        int k=edge[node].val;
        if (k==point[node].father||k==point[node].son) continue;
        dfs_second(k,k);
    }
}

void push_up (int node) {
    tree[node].val=(tree[lnode(node)].val+tree[rnode(node)].val)%p;
}

void push_down (int node) {
    int mid=tree[node].lid+tree[node].rid>>1;
    tree[lnode(node)].tag+=tree[node].tag;
    tree[lnode(node)].val+=tree[node].tag*(mid-tree[node].lid+1);
    tree[lnode(node)].val%=p;
    tree[rnode(node)].tag+=tree[node].tag;
    tree[rnode(node)].val+=tree[node].tag*(tree[node].rid-mid);
    tree[rnode(node)].val%=p;
    tree[node].tag=0;
}

void build (int node,int l,int r) {
    tree[node].tag=0;
    tree[node].lid=l,tree[node].rid=r;
    if (l==r) {
        tree[node].val=in_new[l]%p;
        return ;
    }
    int mid=l+r>>1;
    build(lnode(node),l,mid);
    build(rnode(node),mid+1,r);
    push_up(node);
}

void update (int node,int l,int r,int change) {
    if (l<=tree[node].lid&&tree[node].rid<=r) {
        tree[node].tag+=change;
        tree[node].val+=change*(tree[node].rid-tree[node].lid+1);
        tree[node].val%=p;
        return ;
    }
    push_down(node);
    int mid=tree[node].lid+tree[node].rid>>1;
    if (l<=mid) update(lnode(node),l,r,change);
    if (r>mid) update(rnode(node),l,r,change);
    push_up(node);
}

int query (int node,int l,int r) {
    if (l<=tree[node].lid&&tree[node].rid<=r) return tree[node].val%p;
    push_down(node);
    int res=0,mid=tree[node].lid+tree[node].rid>>1;
    if (l<=mid) res=(res+query(lnode(node),l,r))%p;
    if (r>mid) res=(res+query(rnode(node),l,r))%p;
    return res%p;
}

void update_range (int x,int y,int z) {
    while (point[x].top!=point[y].top) {
        if (point[point[x].top].deep<point[point[y].top].deep) swap(x,y);
        update(1,point[point[x].top].id,point[x].id,z);
        x=point[point[x].top].father;
    }
    if (point[x].deep>point[y].deep) swap(x,y);
    update(1,point[x].id,point[y].id,z);
}

int query_range (int x,int y) {
    int res=0;
    while (point[x].top!=point[y].top) {
        if (point[point[x].top].deep<point[point[y].top].deep) swap(x,y);
        res+=query(1,point[point[x].top].id,point[x].id);
        res%=p;
        x=point[point[x].top].father;
    }
    if (point[x].deep>point[y].deep) swap(x,y);
    res=(res+query(1,point[x].id,point[y].id))%p;
    return res%p;
}

void update_tree (int x,int z) {
    update(1,point[x].id,point[x].id+point[x].siz-1,z);
}

int query_tree (int x) {
    return query(1,point[x].id,point[x].id+point[x].siz-1)%p;
}

signed main (void) {
    scanf("%d %d %d %d",&n,&m,&r,&p);
    for (int i=1;i<=n;++i)
        scanf("%d",&in[i]);
    int x,y,z;
    for (int i=1;i<n;++i){
        scanf("%d %d",&x,&y);
        addedge(x,y),addedge(y,x);
    }
    dfs_first(r,0);
    dfs_second(r,r);
    build(1,1,n);
    for (int i=1;i<=m;++i) {
        scanf("%d",&op);
        if (op==1) {
            scanf("%d %d %d",&x,&y,&z);
            update_range(x,y,z);
        } else if (op==2) {
            scanf("%d %d",&x,&y);
            printf("%d",query_range(x,y));
        } else if (op==3) {
            scanf("%d %d",&x,&z);
            update_tree(x,z);
        } else {
            scanf("%d",&x);
            printf("%d",query_tree(x));
        }
    }
    return 0;
}

by xudongyi1 @ 2024-07-16 10:20:23

@i__ak_io 把所有变量开 long long 试试，可能哪里没有膜到。

by i__ak_io @ 2024-07-16 10:32:56

@xudongyi1 还是不对，样例没过

by xudongyi1 @ 2024-07-16 10:51:58

@i__ak_io push_down 里面 tag 膜一下？

by i__ak_io @ 2024-07-16 11:02:16

@xudongyi1 依然MLE

by i__ak_io @ 2024-07-16 11:10:50

#include <iostream>
#include <cstdio>

using namespace std;

#define lnode(x) x<<1
#define rnode(x) x<<1|1
#define int long long
const int N=1e5+5;

struct Tree {int val,tag,lid,rid;} tree[N<<2];
struct Edge {int val,beg,nex;} edge[N<<1];
struct Point {int son,father,siz,deep,top,id;} point[N];

int n,m,r,p,op;
int tot=0,index=0;
int in[N],in_new[N];

void addedge (int x,int y) {
    edge[++tot].val=y;
    edge[tot].nex=edge[x].beg;
    edge[x].beg=tot;
}

void dfs_first (int node,int fa) {
    point[node].deep=point[fa].deep+1;
    point[node].father=fa;
    point[node].siz=1;
    for (int i=edge[node].beg;i;i=edge[i].nex) {
        int k=edge[i].val;
        if (k==fa) continue;
        dfs_first(k,node);
        point[node].siz+=point[k].siz;
        if (point[point[node].son].siz<point[k].siz) point[node].son=k;
    }
}

void dfs_second (int node,int top) {
    point[node].id=++index;
    in_new[index]=in[node];
    point[node].top=top;
    if (!point[node].son) return ;
    dfs_second(point[node].son,top);
    for (int i=edge[node].beg;i;i=edge[node].nex) {
        int k=edge[node].val;
        if (k==point[node].father||k==point[node].son) continue;
        dfs_second(k,k);
    }
}

void push_up (int node) {
    tree[node].val=(tree[lnode(node)].val+tree[rnode(node)].val)%p;
}

void push_down (int node) {
    int mid=tree[node].lid+tree[node].rid>>1;
    tree[lnode(node)].tag+=tree[node].tag;
    tree[lnode(node)].tag%=p;
    tree[lnode(node)].val+=tree[node].tag*(mid-tree[node].lid+1);
    tree[lnode(node)].val%=p;
    tree[rnode(node)].tag+=tree[node].tag;
    tree[rnode(node)].tag%=p;
    tree[rnode(node)].val+=tree[node].tag*(tree[node].rid-mid);
    tree[rnode(node)].val%=p;
    tree[node].tag=0;
}

void build (int node,int l,int r) {
    tree[node].tag=0;
    tree[node].lid=l,tree[node].rid=r;
    if (l==r) {
        tree[node].val=in_new[l]%p;
        return ;
    }
    int mid=l+r>>1;
    build(lnode(node),l,mid);
    build(rnode(node),mid+1,r);
    push_up(node);
}

void update (int node,int l,int r,int change) {
    if (l<=tree[node].lid&&tree[node].rid<=r) {
        tree[node].tag+=change;
        tree[node].val+=change*(tree[node].rid-tree[node].lid+1);
        tree[node].val%=p;
        return ;
    }
    push_down(node);
    int mid=tree[node].lid+tree[node].rid>>1;
    if (l<=mid) update(lnode(node),l,r,change);
    if (r>mid) update(rnode(node),l,r,change);
    push_up(node);
}

int query (int node,int l,int r) {
    if (l<=tree[node].lid&&tree[node].rid<=r) return tree[node].val%=p;
    push_down(node);
    int res=0,mid=tree[node].lid+tree[node].rid>>1;
    if (l<=mid) res=(res+query(lnode(node),l,r))%p;
    if (r>mid) res=(res+query(rnode(node),l,r))%p;
    return res%p;
}

void update_range (int x,int y,int z) {
    while (point[x].top!=point[y].top) {
        if (point[point[x].top].deep<point[point[y].top].deep) swap(x,y);
        update(1,point[point[x].top].id,point[x].id,z);
        x=point[point[x].top].father;
    }
    if (point[x].deep>point[y].deep) swap(x,y);
    update(1,point[x].id,point[y].id,z);
}

int query_range (int x,int y) {
    int res=0;
    while (point[x].top!=point[y].top) {
        if (point[point[x].top].deep<point[point[y].top].deep) swap(x,y);
        res+=query(1,point[point[x].top].id,point[x].id);
        res%=p;
        x=point[point[x].top].father;
    }
    if (point[x].deep>point[y].deep) swap(x,y);
    res=(res+query(1,point[x].id,point[y].id))%p;
    return res%p;
}

void update_tree (int x,int z) {
    update(1,point[x].id,point[x].id+point[x].siz-1,z);
}

int query_tree (int x) {
    return query(1,point[x].id,point[x].id+point[x].siz-1)%p;
}

signed main (void) {
    scanf("%lld %lld %lld %lld",&n,&m,&r,&p);
    for (int i=1;i<=n;++i)
        scanf("%lld",&in[i]);
    int x,y,z;
    for (int i=1;i<n;++i){
        scanf("%lld %lld",&x,&y);
        addedge(x,y),addedge(y,x);
    }
    dfs_first(r,0);
    dfs_second(r,r);
    build(1,1,n);
    for (int i=1;i<=m;++i) {
        scanf("%lld",&op);
        if (op==1) {
            scanf("%lld %lld %lld",&x,&y,&z);
            update_range(x,y,z);
        } else if (op==2) {
            scanf("%lld %lld",&x,&y);
            printf("%lld\n",query_range(x,y));
        } else if (op==3) {
            scanf("%lld %lld",&x,&z);
            update_tree(x,z);
        } else {
            scanf("%lld",&x);
            printf("%lld\n",query_tree(x));
        }
    }
    return 0;
}