插入一些有利于理解的图片

有关dfn序

关于寻找路径不断往上翻

// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define lson 2*p
#define rson 2*p+1
#define N 200000+110
using namespace std;
int n,m,head[N],sizee[N],deep[N],fa[N],son[N],top[N],w[N],mod,root,cnt,wt[N],id[N],tot;
//------------------------线段树---------------------------------------
struct tree
{
    int left;
    int right;
    int val;
    int sum;
}a[4*N];

void pushup(int p)
{
     a[p].sum=a[2*p].sum+a[2*p+1].sum;
     a[p].sum%=mod;
}
void build(int p,int l,int r)
{
    a[p].left=l;
    a[p].right=r;
    //a[p].val=-1;
    if(l==r){a[p].sum=wt[l];a[p].sum%=mod;return;}
    int mid=(l+r)/2;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
    pushup(p);
}
void pushdown(int p)
{
     if(a[p].val!=0)
    {
        a[2*p].val+=a[p].val;
        a[2*p].sum+=(a[2*p].right-a[2*p].left+1)*a[p].val;
        a[2*p+1].val+=a[p].val;
        a[2*p+1].sum+=(a[2*p+1].right-a[2*p+1].left+1)*a[p].val;
        a[lson].sum%=mod;
        a[rson].sum%=mod;
        a[p].val=0;
    }
}

void update(int p,int l,int r,int d)
{
    if(a[p].left==l&&a[p].right==r){a[p].val+=d;a[p].sum+=(r-l+1)*d;a[p].sum%=mod;return;}
    pushdown(p);
    int mid=(a[p].left+a[p].right)/2;
    if(r<=mid)update(2*p,l,r,d);
    else if(l>mid)update(2*p+1,l,r,d);
         else {update(2*p,l,mid,d);update(2*p+1,mid+1,r,d);}
   pushup(p);
}
int  query(int p,int l,int r)
{
    if(a[p].left==l&&a[p].right==r)return a[p].sum%mod;
   pushdown(p);
    int mid=(a[p].left+a[p].right)/2;
    if(r<=mid)return query(2*p,l,r);
    else if(l>mid)return query(2*p+1,l,r);
         else return query(2*p,l,mid)+query(2*p+1,mid+1,r);
}

//---------------------树链剖分----------------------------------------
struct node
{
    int nt=-1,to;
}edge[N];
void add(int x,int y)
{
    cnt++;
    edge[cnt].to=y;
    edge[cnt].nt=head[x];
    head[x]=cnt;
}
void dfs(int x,int fa1,int d)
{
    deep[x]=d;fa[x]=fa1;sizee[x]=1;
    for(int i=head[x];i!=-1;i=edge[i].nt)
    {
        int v=edge[i].to;
        if(v==fa1)continue;
        dfs(v,x,d+1);
        sizee[x]+=sizee[v];
        if(sizee[v]>sizee[son[x]])son[x]=v;//标记重边
    }
}
void dfs2(int x,int tp)//初始化每个节点所在重边的最小节点，最上面的节点（没有儿子定为自己
{
    id[x]=++tot;
    wt[tot]=w[x];
    top[x]=tp;
    if(!son[x])return;
    dfs2(son[x],tp);
    for(int i=head[x];i!=-1;i=edge[i].nt)
    {
        int v=edge[i].to;
        if(v!=fa[x]&&v!=son[x])
            dfs2(v,v);
    }
}

void uprange(int x,int y,int k)
{
    k%=mod;
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]])swap(x,y);
        update(1,id[top[x]],id[x],k);
        x=fa[top[x]];
    }
    if(deep[x]>deep[y])swap(x,y);
    update(1,id[x],id[y],k);
}
int  qrange(int x,int y)
{
    int ans=0;
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]])swap(x,y);
        ans+=query(1,id[top[x]],id[x]);
        ans%=mod;
        x=fa[top[x]];
    }
    if(deep[x]>deep[y])swap(x,y);
    ans+=query(1,id[x],id[y]);
    return ans%mod;



}
void upson(int x,int k)
{
    k%=mod;
    update(1,id[x],id[x]+sizee[x]-1,k);
}
int qson(int x)
{
    return query(1,id[x],id[x]+sizee[x]-1)%mod;
}
//------------------------主函数---------------------------------------
int main()
{
    memset(head,-1,sizeof(head));
    scanf("%d%d%d%d",&n,&m,&root,&mod);
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    dfs(root,0,1);
    dfs2(root,root);
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int op,x,y,z;
        scanf("%d",&op);
        switch(op)
        {
            case 1:scanf("%d%d%d",&x,&y,&z);uprange(x,y,z);break;
            case 2:scanf("%d%d",&x,&y);printf("%d\n",qrange(x,y));break;
            case 3:scanf("%d%d",&x,&z);
                    upson(x,z);
                    break;
            case 4:scanf("%d",&x);printf("%d\n",qson(x));break;
        }
    }




    return 0;
}