树链剖分滞销，帮帮孩子吧

_Catluo_ @ 2023-04-10 21:02:28

#include<bits/stdc++.h>
#define MAXN (100005)
#define int long long
using namespace std;
int n,m,R,p;
int P[MAXN],a[MAXN];
vector<int>to[MAXN];
int fa[MAXN],dep[MAXN],siz[MAXN],son[MAXN];
int dfs[MAXN],tot,dfn[MAXN],top[MAXN];

void dfs1(int x,int f) {
    dep[x]=dep[f]+1;
    fa[x]=f;
    siz[x]=1;
    for(auto &i:to[x]) {
        if(i==f)continue;
        dfs1(i,x);
        siz[x]+=siz[i];
        if(siz[son[x]]<siz[i])son[x]=i;
    }
    return;
}
void dfs2(int x,int f) {
    top[x]=f;
    dfs[x]=++tot;
    a[tot]=P[x];
    if(son[x])dfs2(son[x],f);
    for(auto &i:to[x]) {
        if(i==fa[x])continue;
        if(i==son[x])continue;
        dfs2(i,i);
    }
    return;
}
//dfs序------------------------------------------------------------------------------------------------------------------------ 

int tree[800005];
int tag[800005];

void build(int x,int l,int r) {
    if(l==r) {
        tree[x]=a[l]%p;
        return;
    }
    int mid=(l+r)/2;
    build(x*2,l,mid);
    build(x*2+1,mid+1,r);
    tree[x]=(tree[x*2]+tree[x*2+1])%p;
}

void push_down(int x,int l,int r) {
    int mid=(l+r)/2;
    tree[x*2]=(tree[x*2]+((tag[x]*(mid-l+1))%p))%p;
    tree[x*2+1]=(tree[x*2+1]+((tag[x]*(r-mid))%p))%p;
    tag[x*2]=(tag[x*2]+tag[x])%p;
    tag[x*2+1]=(tag[x*2+1]+tag[x])%p;
    tag[x]=0;
}

void add(int x,int l,int r,int L,int R,int v) {
    if(L<=l&&r<=R) {
        tree[x]=(tree[x]+(((r-l+1)*v)%p))%p;
        tag[x]=(tag[x]+v)%p;
        return;
    }
    if(r<L||R<l)return;
    push_down(x,l,r);
    int mid=(l+r)/2;
    add(x*2,l,mid,L,R,v);
    add(x*2+1,mid+1,r,L,R,v);
    tree[x]=(tree[x*2]+tree[x*2+1])%p;
}

int q(int x,int l,int r,int L,int R) {
    push_down(x,l,r);
    if(L<=l&&r<=R)return tree[x]%p;
    if(r<L||R<l)return 0;
    int mid=(l+r)/2;
    return (q(x*2,l,mid,L,R)+q(x*2+1,mid+1,r,L,R))%p;
}
//线段树--------------------------------------------------------------------------------- 

signed main() {
    scanf("%lld %lld %lld %lld",&n,&m,&R,&p);
    for(int i=1; i<=n; i++)scanf("%lld",&P[i]);
    for(int i=1; i<n; i++) {
        int x,y;
        scanf("%lld %lld",&x,&y);
        to[x].push_back(y);
        to[y].push_back(x);
    }
    dfs1(R,0);
    dfs2(R,R);
    build(1,1,n);
    while(m--) {
        int op;
        cin>>op;
        if(op==1) {
            int x,y,z;
            scanf("%lld %lld %lld",&x,&y,&z);
            while(top[x]!=top[y]) {
                if(dep[top[x]]<dep[top[y]])swap(x,y);
                add(1,1,n,dfs[top[x]],dfs[x],z%p);
                x=fa[top[x]];
            }
            if(dep[x]<dep[y])swap(x,y);
            add(1,1,n,dfs[y],dfs[x],z%p);
        }
        if(op==2) {
            int x,y;
            scanf("%lld %lld",&x,&y);
            int res=0;
            while(top[x]!=top[y]) {
                if(dep[top[x]]<dep[top[y]])swap(x,y);
                res=(res+q(1,1,n,dfs[top[x]],dfs[x]))%p;
                x=fa[top[x]];
            }
            if(dep[x]<dep[y])swap(x,y);
            res=(res+q(1,1,n,dep[y],dep[x]))%p;
            printf("%lld\n",res);
        }
        if(op==3) {
            int x,z;
            scanf("%lld %lld",&x,&z);
            add(1,1,n,dfs[x],dfs[x]+siz[x]-1,z%p);
        }
        if(op==4) {
            int x;
            scanf("%lld",&x);
            int res=q(1,1,n,dfs[x],dfs[x]+siz[x]-1)%p;
            printf("%lld\n",res);
        }
//      cout<<"-------------------------------------------------------"<<endl;
//      for(int i=1; i<=n; i++)cout<<i<<" ";
//      cout<<endl;
//      for(int i=1; i<=n; i++)cout<<q(1,1,n,dfs[i],dfs[i])<<" ";
//      cout<<endl;
//      cout<<"-------------------------------------------------------"<<endl;
    }
    return 0;
}

by Xy_top @ 2023-04-10 21:07:02

@ljhdsb op == 2 的 query 参数有问题，你自己看吧

by Xy_top @ 2023-04-10 21:07:43

@ljhdsb 改好就过了，（给个关注呗！）

#include<bits/stdc++.h>
#define MAXN (100005)
#define int long long
using namespace std;
int n,m,R,p;
int P[MAXN],a[MAXN];
vector<int>to[MAXN];
int fa[MAXN],dep[MAXN],siz[MAXN],son[MAXN];
int dfs[MAXN],tot,dfn[MAXN],top[MAXN];

void dfs1(int x,int f) {
    dep[x]=dep[f]+1;
    fa[x]=f;
    siz[x]=1;
    for(auto &i:to[x]) {
        if(i==f)continue;
        dfs1(i,x);
        siz[x]+=siz[i];
        if(siz[son[x]]<siz[i])son[x]=i;
    }
    return;
}
void dfs2(int x,int f) {
    top[x]=f;
    dfs[x]=++tot;
    a[tot]=P[x];
    if(son[x])dfs2(son[x],f);
    for(auto &i:to[x]) {
        if(i==fa[x])continue;
        if(i==son[x])continue;
        dfs2(i,i);
    }
    return;
}
//dfs序------------------------------------------------------------------------------------------------------------------------ 

int tree[800005];
int tag[800005];

void build(int x,int l,int r) {
    if(l==r) {
        tree[x]=a[l]%p;
        return;
    }
    int mid=(l+r)/2;
    build(x*2,l,mid);
    build(x*2+1,mid+1,r);
    tree[x]=(tree[x*2]+tree[x*2+1])%p;
}

void push_down(int x,int l,int r) {
    int mid=(l+r)/2;
    tree[x*2]=(tree[x*2]+((tag[x]*(mid-l+1))%p))%p;
    tree[x*2+1]=(tree[x*2+1]+((tag[x]*(r-mid))%p))%p;
    tag[x*2]=(tag[x*2]+tag[x])%p;
    tag[x*2+1]=(tag[x*2+1]+tag[x])%p;
    tag[x]=0;
}

void add(int x,int l,int r,int L,int R,int v) {
    if(L<=l&&r<=R) {
        tree[x]=(tree[x]+(((r-l+1)*v)%p))%p;
        tag[x]=(tag[x]+v)%p;
        return;
    }
    if(r<L||R<l)return;
    push_down(x,l,r);
    int mid=(l+r)/2;
    add(x*2,l,mid,L,R,v);
    add(x*2+1,mid+1,r,L,R,v);
    tree[x]=(tree[x*2]+tree[x*2+1])%p;
}

int q(int x,int l,int r,int L,int R) {
    push_down(x,l,r);
    if(L<=l&&r<=R)return tree[x]%p;
    if(r<L||R<l)return 0;
    int mid=(l+r)/2;
    return (q(x*2,l,mid,L,R)+q(x*2+1,mid+1,r,L,R))%p;
}
//线段树--------------------------------------------------------------------------------- 

signed main() {
    scanf("%lld %lld %lld %lld",&n,&m,&R,&p);
    for(int i=1; i<=n; i++)scanf("%lld",&P[i]);
    for(int i=1; i<n; i++) {
        int x,y;
        scanf("%lld %lld",&x,&y);
        to[x].push_back(y);
        to[y].push_back(x);
    }
    dfs1(R,0);
    dfs2(R,R);
    build(1,1,n);
    while(m--) {
        int op;
        cin>>op;
        if(op==1) {
            int x,y,z;
            scanf("%lld %lld %lld",&x,&y,&z);
            while(top[x]!=top[y]) {
                if(dep[top[x]]<dep[top[y]])swap(x,y);
                add(1,1,n,dfs[top[x]],dfs[x],z%p);
                x=fa[top[x]];
            }
            if(dep[x]<dep[y])swap(x,y);
            add(1,1,n,dfs[y],dfs[x],z%p);
        }
        if(op==2) {
            int x,y;
            scanf("%lld %lld",&x,&y);
            int res=0;
            while(top[x]!=top[y]) {
                if(dep[top[x]]<dep[top[y]])swap(x,y);
                res=(res+q(1,1,n,dfs[top[x]],dfs[x]))%p;
                x=fa[top[x]];
            }
            if(dep[x]<dep[y])swap(x,y);
            res=(res+q(1,1,n,dfs[y],dfs[x]))%p;
            printf("%lld\n",res);
        }
        if(op==3) {
            int x,z;
            scanf("%lld %lld",&x,&z);
            add(1,1,n,dfs[x],dfs[x]+siz[x]-1,z%p);
        }
        if(op==4) {
            int x;
            scanf("%lld",&x);
            int res=q(1,1,n,dfs[x],dfs[x]+siz[x]-1)%p;
            printf("%lld\n",res);
        }
//      cout<<"-------------------------------------------------------"<<endl;
//      for(int i=1; i<=n; i++)cout<<i<<" ";
//      cout<<endl;
//      for(int i=1; i<=n; i++)cout<<q(1,1,n,dfs[i],dfs[i])<<" ";
//      cout<<endl;
//      cout<<"-------------------------------------------------------"<<endl;
    }
    return 0;
}

by Liquefyx @ 2023-04-10 21:17:27

%%%

by 良心WA题人 @ 2023-04-10 21:18:16

%%%

by _Catluo_ @ 2023-04-10 21:21:09

@Xy_top 我是瞎子,找了一个多小时了,还没发现

by _Catluo_ @ 2023-04-10 21:21:54

@Xy_top 我这种地方都能打错,唉...

by Xy_top @ 2023-04-12 21:15:12

@ljhdsb 所以能不能给本蒟蒻一个关注呢？调代码不易。（不想的话也没事儿，我只是一个蒟蒻）

by _Catluo_ @ 2023-04-12 21:15:47

@Xy_top 已关注

by Xy_top @ 2023-04-12 21:17:08

@ljhdsb 已互关