P3384树链剖分模板题_C

概述https://www.luogu.org/problem/P3384 #include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=100000+10;const int M=N;int head[N],ver[2*M],nex[2*M],tot=1;inline void add(

https://www.luogu.org/problem/P3384

#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=100000+10;const int M=N;int head[N],ver[2*M],nex[2*M],tot=1;inline voID add(int x,int y){    ver[++tot]=y;    nex[tot]=head[x];    head[x]=tot;}int n,m,r,p;ll w[N];int f[N],d[N],sz[N],son[N],dfn[N],rk[N],top[N],_cnt;voID dfs1(int x,int depth)//计算父节点，深度，子树大小，重儿子。{    d[x]=depth;    sz[x]=1;    for(int i=head[x];i;i=nex[i])    {        int y=ver[i];        if(f[x]==y)continue;        f[y]=x;        dfs1(y,depth+1);        sz[x]+=sz[y];        if(sz[y]>sz[son[x]])            son[x]=y;    }}voID dfs2(int x,int t)//计算dfn,rk,top;{    top[x]=t;    dfn[x]=++_cnt;//dfn序    rk[_cnt]=x;//dfn对应节点    if(!son[x])        return;    dfs2(son[x],t);//重儿子优先    for(int i=head[x];i;i=nex[i])    {        int y=ver[i];        if(y!=son[x]&&y!=f[x])            dfs2(y,y);    }}ll dat[N*4],tag[N*4];inline voID push_down(int k,int l,int r){    int m=(l+r)>>1,lc=2*k,rc=2*k+1;    if(tag[k])    {        (tag[lc]+=tag[k])%=p;        (tag[rc]+=tag[k])%=p;        (dat[lc]+=tag[k]*(m-l+1))%=p;        (dat[rc]+=tag[k]*(r-m))%=p;        tag[k]=0;    }}inline voID push_up(int k){    dat[k]=(dat[2*k]+dat[2*k+1])%p;}voID build(int k,int r){    if(l==r)    {        dat[k]=w[rk[l]]%p;        return;    }    int m=(l+r)>>1,rc=2*k+1;    build(lc,l,m);    build(rc,m+1,r);    push_up(k);}voID update(int v,int a,int b,int k,int r){    if(a<=l&&b>=r)    {        tag[k]+=v;        dat[k]+=v*(r-l+1);        return;    }    push_down(k,r);    int m=(l+r)>>1,rc=2*k+1;    if(a<=m)update(v,a,b,lc,m);    if(b>m)update(v,rc,m+1,r);    push_up(k);}ll query(int a,int r){    if(a<=l&&b>=r)        return dat[k];    int m=(l+r)>>1,rc=2*k+1;    ll ans=0;    push_down(k,r);    if(a<=m)ans+=query(a,m);    if(b>m)ans+=query(a,r);    return ans;}ll sum(int x,int y){    ll ans=0;    while(top[x]!=top[y])    {        if(d[top[x]]<d[top[y]])            swap(x,y);        ans=(ans+query(dfn[top[x]],dfn[x],1,n))%p;        x=f[top[x]];    }    if(dfn[x]>dfn[y])        swap(x,y);    ans=(ans+query(dfn[x],dfn[y],n))%p;    return ans;}voID change(int v,int x,int y){    while(top[x]!=top[y])    {        if(d[top[x]]<d[top[y]])            swap(x,y);        update(v,dfn[top[x]],1,1,n);        x=f[top[x]];    }    if(dfn[x]>dfn[y])        swap(x,y);    update(v,n);}int main(){    scanf("%d%d%d%d",&n,&m,&r,&p);    for(int i=1;i<=n;++i)        scanf("%lld",w+i);    for(int i=1;i<n;++i)    {        int x,y;        scanf("%d%d",&x,&y);        add(x,y);        add(y,x);    }    dfs1(r,1);    dfs2(r,r);    build(1,n);    for(int i=0;i<m;++i)    {        int op;        scanf("%d",&op);        if(op==1)        {            int x,y,z;            scanf("%d%d%d",&y,&z);            change(z,x,y);        }        else if(op==2)        {            int x,y;            scanf("%d%d",&y);            printf("%lld\n",sum(x,y));        }        else if(op==3)        {            int x,z;            scanf("%d%d",&z);            update(z,dfn[x]+sz[x]-1,n);        }        else        {            int x;            scanf("%d",&x);            printf("%lld\n",query(dfn[x],dfn[x]+sz[x]-1,n)%p);        }    }    return 0;}