求助，感觉没错但是build就出问题了

UQAQU @ 2024-08-10 17:34:54

#include<bits/stdc++.h>
#define ll long long int
using namespace std;
const int N=1e5+7;
ll n,m,s,mod;
struct terr{
    ll to,next;
}edge[N];
ll head[N],cnt=0;
ll top[N],father[N],son[N],val[N],id[N],num[N],size[N],deep[N],cnt1=0;
ll d[N],lazy[N];
void add_edge(ll u,ll v){
    cnt++;
    edge[cnt].to=v,edge[cnt].next=head[u],head[u]=cnt;
}
void dfs1(int u){
    size[u]=1;
    for (ll i=head[u];i!=0;i=edge[i].next){
        ll v=edge[i].to;
        if (!deep[v]){
            deep[v]=deep[u]+1;
            father[v]=u;
            dfs1(v);
            size[u]+=size[v];
            if (size[v]>size[son[u]]){
                son[u]=v;
            }
        }
    }
    return ;
}
void dfs2(int u,int tp){
    ++cnt1;
    id[u]=cnt1;
    val[cnt1]=num[u];
    top[u]=tp;
    if (son[u]){
        dfs2(son[u],tp);
    }
    for (ll i=head[u];i!=0;i=edge[i].next){
        ll v=edge[i].to;
        if (v!=father[u] && v!=son[u]){
            dfs2(v,v);
        }
    }
    return ;
}
void push(int l,int r,int p){
    ll mid=(l+r)>>1;
    d[2*p]+=lazy[p]*(mid-l+1),d[2*p]%=mod;
    d[2*p+1]+=lazy[p]*(r-mid),d[2*p+1]%=mod;
    lazy[2*p]+=lazy[p],lazy[2*p]%=mod;
    lazy[2*p+1]+=lazy[p],lazy[2*p+1]%=mod;
    lazy[p]=0;
    return ;
}
void build(ll l,ll r,ll p){
    if (l==r){
        d[p]=val[l];
        return ;
    }
    ll mid=(l+r)>>1;
    build(l,mid,2*p);
    build(mid+1,r,2*p+1);
    d[p]=d[2*p]+d[2*p+1];
    d[p]%=mod;
    return ;
}
void update(ll l,ll r,ll s,ll t,ll up,ll p){
    if (l<=s && r>=t){
        d[p]+=up*(t-s+1),d[p]%=mod;
        lazy[p]+=up,lazy[p]%=mod;
        return ;
    }
    ll mid=(s+t)>>1;
    if (lazy[p]){
        push(s,t,p);
    }
    if (mid>=l){
        update(l,r,s,mid,up,2*p);
    }
    if (mid<r){
        update(l,r,mid+1,t,up,2*p+1);
    }
    d[p]=(d[2*p]+d[2*p+1])%mod;
    return ;
}
ll query(ll l,ll r,ll s,ll t,ll p){
    if (l<=s && r>=t){
        return d[p]%=mod;
    }
    ll mid=(s+t)>>1;
    if (lazy[p]){
        push(s,t,p);
    }
    ll a=0,b=0;
    if (mid>=l){
        a=query(l,r,s,mid,2*p);
    }
    if (r>mid){
        b=query(l,r,mid+1,r,2*p+1);
    }
    return (a%mod+b%mod)%mod;
}
ll query1(ll x,ll y){
    ll tot=0;
    while (top[x]!=top[y]){
        if (deep[top[x]]<deep[top[y]]){
            swap(x,y);
        }
        tot+=query(id[top[x]],id[x],1,cnt1,1);
        x=father[top[x]];
    }
    if (id[x]>id[y]){
        swap(x,y);
    }
    tot+=query(id[x],id[y],1,cnt1,1);
    return tot;
}
void query2(int x,int y,int z){
    while (top[x]!=top[y]){
        if (deep[top[x]]<deep[top[y]]){
            swap(x,y);
        }
        update(id[top[x]],id[x],1,cnt1,z,1);
        x=father[top[x]];
    }
    if (id[x]>id[y]){
        swap(x,y);
    }
    update(id[x],id[y],1,cnt1,z,1);
}
int main()
{
    ll n,m,s,mod;
    cin>>n>>m>>s>>mod;
    for (ll i=1;i<=n;i++){
        cin>>num[i];
        num[i]%=mod;
    }
    for (ll i=1;i<n;i++){
        ll x,y;
        cin>>x>>y;
        add_edge(x,y);
        add_edge(y,x);
    }
    deep[s]=1,father[s]=1;
    dfs1(s);
    dfs2(s,s);
    build(1,n,1);
    while (m--){
        ll sz;
        cin>>sz;
        if (sz==1){
            ll x,y,z;
            cin>>x>>y>>z;
            query2(x,y,z%mod);
        }
        if (sz==2){
            ll x,y;
            cin>>x>>y;
            cout<<query1(x,y)%mod<<endl;
        }
        if (sz==3){
            ll x,y;
            cin>>x>>y;
            update(id[x],id[x]+size[x]-1,1,n,y%mod,1);
        }
        if (sz==4){
            ll x;
            cin>>x;
            cout<<query(id[x],id[x]+size[x]-1,1,n,1)%mod<<endl;
        }
    }
    return 0;
}

by UQAQU @ 2024-08-10 17:36:04

样例都没过

by _Supernova @ 2024-08-10 17:42:59

Build 函数中，当 l=r 时，你的赋值有问题。 注意，线段树是对 dfn 序建的，不是对原节点编号建的。

by UQAQU @ 2024-08-10 20:05:11

@XX_Traveller_XX

#include<bits/stdc++.h>
#define ll long long int
using namespace std;
const int N=1e5+7;
const ll inf=2147483647;
struct tree{
    ll to,next;
}edge[N];
ll head[N],cnt=0;
ll top[N],father[N],son[N],val[N],id[N],num[N],size[N],deep[N],cnt1=0;
ll d[N],lazy[N];
int n,m,s,mod;
void add_edge(ll u,ll v){
    cnt++;
    edge[cnt].to=v,edge[cnt].next=head[u],head[u]=cnt;
}
void dfs1(int u){
    size[u]=1;
    for (ll i=head[u];i!=0;i=edge[i].next){
        ll v=edge[i].to;
        if (!deep[v]){
            deep[v]=deep[u]+1;
            father[v]=u;
            dfs1(v);
            size[u]+=size[v];
            if (size[v]>size[son[u]]){
                son[u]=v;
            }
        }
    }
    return ;
}
void dfs2(int u,int tp){
    ++cnt1;
    id[u]=cnt1;
    val[cnt1]=num[u];
    top[u]=tp;
    if (son[u]){
        dfs2(son[u],tp);
    }
    for (ll i=head[u];i!=0;i=edge[i].next){
        ll v=edge[i].to;
        if (v!=father[u] && v!=son[u]){
            dfs2(v,v);
        }
    }
    return ;
}
void push(int l,int r,int p){
    ll mid=(l+r)>>1;
    d[2*p]+=lazy[p]*(mid-l+1),d[2*p]%=mod;
    d[2*p+1]+=lazy[p]*(r-mid),d[2*p+1]%=mod;
    lazy[2*p]+=lazy[p],lazy[2*p]%=mod;
    lazy[2*p+1]+=lazy[p],lazy[2*p+1]%=mod;
    lazy[p]=0;
    return ;
}
void build(ll l,ll r,ll p){
    if (l==r){
        d[p]=val[l];
        return ;
    }
    ll mid=(l+r)>>1;
    build(l,mid,2*p);
    build(mid+1,r,2*p+1);
    d[p]=d[2*p]+d[2*p+1];
    d[p]%=mod;
    return ;
}
void update(ll l,ll r,ll s,ll t,ll up,ll p){
    if (l<=s && r>=t){
        d[p]+=up*(t-s+1),d[p]%=mod;
        lazy[p]+=up,lazy[p]%=mod;
        return ;
    }
    ll mid=(s+t)>>1;
    if (lazy[p] ){
        push(s,t,p);
    }
    if (mid>=l){
        update(l,r,s,mid,up,2*p);
    }
    if (mid<r){
        update(l,r,mid+1,t,up,2*p+1);
    }
    d[p]=(d[2*p]+d[2*p+1])%mod;
    return ;
}
ll query(ll l,ll r,ll s,ll t,ll p){
    if (l<=s && r>=t){
        return d[p]%=mod;
    }
    ll mid=(s+t)>>1;
    if (lazy[p]){
        push(s,t,p);
    }
    ll a=0,b=0;
    if (mid>=l){
        a=query(l,r,s,mid,2*p);
    }
    if (r>mid){
        b=query(l,r,mid+1,r,2*p+1);
    }
    return (a%mod+b%mod)%mod;
}
int query1(int x,int y){
    ll tot=0;
    while (top[x]!=top[y]){
        if (deep[top[x]]<deep[top[y]]){
            swap(x,y);
        }
        tot+=query(id[top[x]],id[x],1,cnt1,1);
        x=father[top[x]];
    }
    if (id[x]>id[y]){
        swap(x,y);
    }
    tot+=query(id[x],id[y],1,cnt1,1);
    return tot;
}
void query2(int x,int y,int z){
    while (top[x]!=top[y]){
        if (deep[top[x]]<deep[top[y]]){
            swap(x,y);
        }
        update(id[top[x]],id[x],1,cnt1,z,1);
        x=father[top[x]];
    }
    if (id[x]>id[y]){
        swap(x,y);
    }
    update(id[x],id[y],1,cnt1,z,1);
}
int main()
{
    cin>>n>>m>>s>>mod;
    for (ll i=1;i<=n;i++){
        cin>>num[i];
        num[i]%=mod;
    }
    for (ll i=1;i<n;i++){
        ll x,y;
        cin>>x>>y;
        add_edge(x,y);
        add_edge(y,x);
    }
    deep[s]=1,father[s]=1;
    dfs1(s);
    dfs2(s,s);
    build(1,n,1);
    while (m--){
        ll sz;
        cin>>sz;
        if (sz==1){
            ll x,y,z;
            cin>>x>>y>>z;
            query2(x,y,z%mod);
        }
        if (sz==2){
            ll x,y;
            cin>>x>>y;
            cout<<query1(x,y)%mod<<endl;
        }
        if (sz==3){
            ll x,y;
            cin>>x>>y;
            update(id[x],id[x]+size[x]-1,1,n,y%mod,1);
        }
        if (sz==4){
            ll x;
            cin>>x;
            cout<<query(id[x],id[x]+size[x]-1,1,n,1)%mod<<endl;
        }
    }
    return 0;
}

我改了一下，现在是swap函数在调试时会跳库