树链剖分 37 pts 求助（悬关）

#include <bits/stdc++.h>
using namespace std;
struct edge
{
    long long v,nxt;
}e[800000];
struct node
{
    long long l,r,v,ad;
}tr[800000];
long long n,m,r,mod,op,x,y,z,a[300000],c[300000],h[300000],cnt=0,root=0;
long long lc[800000],rc[800000];
long long dep[300000],fa[300000],siz[300000],hs[300000],id[300000],top[300000],tol=0;
void add_edge(long long u,long long v)
{
    e[++cnt].nxt=h[u];
    e[cnt].v=v;
    h[u]=cnt;
}

void pushup(long long x)
{
    tr[x].v=(tr[lc[x]].v+tr[rc[x]].v)%mod;
}

void pushdown(long long x)
{
    tr[x].v=(tr[x].v+tr[x].ad*(tr[x].r-tr[x].l+1)%mod)%mod;
    tr[lc[x]].ad=(tr[lc[x]].ad+tr[x].ad)%mod,tr[rc[x]].ad=(tr[rc[x]].ad+tr[x].ad)%mod,tr[x].ad=0;
}

void build(long long now,long long l,long long r)
{
    tr[now].l=l,tr[now].r=r;
    lc[now]=now*2,rc[now]=now*2+1;
    if(l==r)
       {
        tr[now].v=a[l]%mod;
        return;
       }
    long long mid=(l+r)/2;
    build(lc[now],l,mid),build(rc[now],mid+1,r);
    pushup(now);
}

void add(long long now,long long l,long long r,long long k)
{
    pushdown(now);
    if(tr[now].l>=l&&tr[now].r<=r)
       {
        tr[now].ad+=k;
        return;
       }
    long long mid=(tr[now].l+tr[now].r)/2;
    if(l<=mid)add(lc[now],l,r,k);
    if(r>=mid+1)add(rc[now],l,r,k);
    pushdown(lc[now]);pushdown(rc[now]);
    pushup(now);
}

long long query(long long now,long long l,long long r)
{
    pushdown(now);
    long long ans=0;
    if(tr[now].l>=l&&tr[now].r<=r)return tr[now].v;
    long long mid=(tr[now].l+tr[now].r)/2;
    if(l<=mid)ans+=query(lc[now],l,r);
    if(r>=mid+1)ans+=query(rc[now],l,r);
    return ans;
}

void dfs1(long long x,long long f)
{
    long long mx=0,ans=0;
    dep[x]=dep[f]+1,fa[x]=f,siz[x]=1;
    for(int i=h[x];i;i=e[i].nxt)
        if(e[i].v!=f)
            {
                dfs1(e[i].v,x);
                if(siz[e[i].v]>ans)mx=siz[e[i].v],ans=e[i].v;
                siz[x]+=siz[e[i].v];
            }
    hs[x]=ans;
}

void dfs2(long long x,long long f,long long tf)
{
    id[x]=++tol,a[id[x]]=c[x],top[x]=tf;
    if(hs[x]!=0)dfs2(hs[x],x,tf);
    for(int i=h[x];i;i=e[i].nxt)
        if(e[i].v!=f&&e[i].v!=hs[x])dfs2(e[i].v,x,e[i].v);
}

void radd(long long x,long long y,long long z)
{
    while(top[x]!=top[y])
       {
       if(dep[top[x]]>dep[top[y]])swap(x,y);
       add(root,id[top[y]],id[y],z);
       y=fa[top[y]];
       }
    if(dep[x]>dep[y])swap(x,y);
    add(root,id[x],id[y],z);
}

long long rquery(long long x,long long y)
{
    long long ans=0;
    while(top[x]!=top[y])
       {
       if(dep[top[x]]>dep[top[y]])swap(x,y);
       ans=(ans+query(root,id[top[y]],id[y]))%mod;
       y=fa[top[y]];
       }
    if(dep[x]>dep[y])swap(x,y);
    ans=(ans+query(root,id[x],id[y]))%mod;
    return ans;
}

void sadd(long long x,long long z)
{
    add(root,id[x],id[x]+siz[x]-1,z);
}

long long squery(long long x)
{
    return query(root,id[x],id[x]+siz[x]-1);
}

int main()
{
    scanf("%lld%lld%lld%lld",&n,&m,&r,&mod);
    for(int i=1;i<=n;i++)scanf("%lld",&c[i]);
    for(int i=1;i<=n-1;i++)
        {
            scanf("%lld%lld",&x,&y);
            add_edge(x,y),add_edge(y,x);
        }
    dfs1(r,0),dfs2(r,0,0),n=tol,root=1;
    build(root,1,n);
    for(int i=1;i<=m;i++)
        {
            scanf("%lld",&op);
            if(op==1)
               {
               scanf("%lld%lld%lld",&x,&y,&z);
               radd(x,y,z);
               }
            else if(op==2)
               {
                scanf("%lld%lld",&x,&y);
                printf("%lld\n",rquery(x,y));
               }
            else if(op==3)
               {
                scanf("%lld%lld",&x,&z);
                sadd(x,z);
               }
            else if(op==4)
               {
                scanf("%lld",&x);
                printf("%lld\n",squery(x));
               }
        }
    return 0;
}

目测线段树应该是对的，不仅有 WA，还有 TLE。