1.前言:

以前初学者都会认为树链剖分是个很难的算法,其实很简单.大致思想就是把树分成链,然后用线段树进行一定操作即可.只是代码稍微有点长.

2.算法流程:

1.首先对于这颗树的每个点找到它的重儿子,树链剖分需要重构一下这颗树让重儿子的节点优先跑出,这里只需要一个dfs即可.
2.重构完树了之后呢?就只要把这颗树按节点序号投影到线段树即可.然后用线段树的操作来对于树进行操作.
3.对于模板题 一个很显然的结论,在树重构了之后,我对于子树u进行操作就是对于线段树区间(u,u+siz[u]-1)进行操作.然后对于树上路径是唯一的,我们可以采用倍增的思想对于u->v这条路径进行操作,这里我们需要记录一个东西,就是重链的起点是哪里,对于不是一颗重链的点,我们就可以一直跳.比较一下深度即可.

3.时间复杂度分析:

因为假如u->v为轻边,那么siz[v]<siz[u]/2的,否则为重边,如此可以判断轻边数量不超过logn的,然后线段树查询时logn的,所以时间复杂度就是的.

4.代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+500;
ll n,m,r,p;
ll w[N];
vector<int>v[N];
ll dep[N],siz[N],dfn[N],f[N];
//跑出深度,子树大小,重儿子,父亲. 
void dfs1(int u,int fa)
{
    siz[u]=1;dep[u]=dep[fa]+1;f[u]=fa;
    int num=v[u].size();
    for(int i=0;i<num;i++)
    {
        int son=v[u][i];
        if(son==fa)    continue;
        dfs1(son,u);
        siz[u]+=siz[son];
        if(siz[son]>siz[dfn[u]])    dfn[u]=son;
    }
}

//跑出每个节点的下标以及处理它们的权值,然后统计重链的起点. 
ll id=0,idx[N],top[N],val[N];
void dfs2(int u,int topf)
{
    idx[u]=++id;
    top[u]=topf;
    val[id]=w[u];
    if(!dfn[u])    return;
    dfs2(dfn[u],topf);
    int num=v[u].size();
    for(int i=0;i<num;i++)
    {
        int son=v[u][i];
        if(idx[son])    continue;
        dfs2(son,son);
    }
}

//写一份有线段树区间修改,区间求和功能的树. 
struct Tree{
    ll l,r,len,sum,lazy;
}tr[N<<2];
void pushup(int u)
{
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}

void pushdown(int u)
{
    tr[u<<1].sum=(tr[u<<1].sum+tr[u].lazy*tr[u<<1].len%p)%p;
    tr[u<<1|1].sum=(tr[u<<1|1].sum+tr[u].lazy*tr[u<<1|1].len%p)%p;
    tr[u<<1].lazy=(tr[u<<1].lazy+tr[u].lazy)%p;
    tr[u<<1|1].lazy=(tr[u<<1|1].lazy+tr[u].lazy)%p;
    tr[u].lazy=0;
}
void build(int u,int l,int r)
{
    tr[u].len=(r-l+1);tr[u].l=l;tr[u].r=r;
    if(l==r)
    {
        tr[u].l=tr[u].r=l;
        tr[u].sum=val[l];
        return;
    }int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}

void add(int u,int L,int R,int k)
{
    if(tr[u].r<L||R<tr[u].l)    return;
    if(L<=tr[u].l&&tr[u].r<=R)
    {
        tr[u].sum=(tr[u].sum+k*(tr[u].len)%p)%p;
        tr[u].lazy=(tr[u].lazy+k)%p;
        return;
    }pushdown(u);
    add(u<<1,L,R,k);
    add(u<<1|1,L,R,k);
    pushup(u);
}

ll query(int u,int L,int R)
{
    if(tr[u].r<L||R<tr[u].l)    return 0;
    if(L<=tr[u].l&&tr[u].r<=R)    return tr[u].sum%p;
    pushdown(u);
    return (query(u<<1,L,R)+query(u<<1|1,L,R))%p;
}

//实现v->u的修改以及查询操作.
void Treeadd(int x,int y,int k)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])    swap(x,y);
        add(1,idx[top[x]],idx[x],k);
        x=f[top[x]];
    }
    if(dep[x]>dep[y])    swap(x,y);
    add(1,idx[x],idx[y],k);
}

ll Treesum(int x,int y)
{
    ll ans=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])    swap(x,y);
        ans=(ans+query(1,idx[top[x]],idx[x]))%p;
        x=f[top[x]];
    }
    if(dep[x]>dep[y])    swap(x,y);
    ans=(ans+query(1,idx[x],idx[y]))%p;
    return ans;
}

int main()
{
    scanf("%lld%lld%lld%lld",&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);
        v[x].push_back(y);
        v[y].push_back(x);
    }    
    dfs1(r,r);
    dfs2(r,r);
    build(1,1,n);
    while(m--)
    {
        int op,x,y,z;
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%d",&x,&y,&z);
            Treeadd(x,y,z%p);
        }
        else if(op==2)
        {
            scanf("%d%d",&x,&y);
            printf("%lld\n",Treesum(x,y));
        }
        else if(op==3)
        {
            scanf("%d%d",&x,&z);
            add(1,idx[x],idx[x]+siz[x]-1,z%p);
        }
        else
        {
            scanf("%d",&x);
            printf("%lld\n",query(1,idx[x],idx[x]+siz[x]-1));
        }
    }
    return 0;    
}