树链剖分 RE on 1~10 马蜂良好玄关球调

# include <bits/stdc++.h>
# include <iostream>

using namespace std;

struct Node
{
  int p;
  struct Node* nxt;
};
struct Head
{
    int data;
    struct Node* nxt;
};

int a[100005],b[100005]; // 按新下标排序的新数组
struct Head p[100005];
int fa[100005];
int dep[100005];
int tot[100005];
int son[100005];
int idx[100005];
int top[100005];
int cnt;
int n,m,r;
long long mod;
long long Tree[100005*4];
long long tag[100005*4];

void add_tag(int node,int l,int r,int k)
{
     tag[node] += k;
    Tree[node] += (r-l+1)*k;
    return ;
}

void push_down(int node,int l,int r)
{
    if (tag[node])
    {
        int mid = (l + r) / 2;
        add_tag(node*2,l,mid,tag[node]);
        add_tag(node*2+1,mid+1,r,tag[node]);
        tag[node] = 0;
    }
    return ;
}

void Build(int node,int l,int r)
{
    if (l == r)
    {
        Tree[node] = a[l];
        return ;
    }

    int mid = (l+r) /2;
    Build(node*2,l,mid);
    Build(node*2+1,mid+1,r);

    Tree[node] = Tree[node*2] + Tree[node*2+1];

    return  ;
}

void add(int node,int l,int r,int tl,int tr,int w)
{
    if (tl <= l && tr >= r)
    {
        add_tag(node,l,r,w);
        return ;
    }

    push_down(node,l,r);
    int mid = (l+r) / 2;

    if (mid  >= tl)
    {
        add(node*2,l,mid,tl,tr,w);
    }
    if (mid < tr)
    {
        add(node*2+1,mid+1,r,tl,tr,w);
    }

    Tree[node] = Tree[node*2] + Tree[node*2+1];

    return ;
}

long long query(int node,int l,int r,int tl,int tr)
{
    if (tl <= l && r <= tr)
    {
        return Tree[node];
    }

    push_down(node,l,r);
    int mid = (l+r) / 2;
    long long res = 0;

    if (mid >= tl)
    {
        res += query(node*2,l,mid,tl,tr);
    }
    if (mid < tr)
    {
        res += query(node*2+1,mid+1,r,tl,tr);
    }

    return res;
}

struct Node* ini()
{
    struct Node* tmp = (struct Node*) malloc (sizeof(struct Node));
    tmp->nxt = NULL;
    return tmp;
}

void add_edge(int x,int y)
{
    struct Node* tmp1 = ini();
    tmp1->p = y;
    tmp1->nxt = p[x].nxt;
    struct Node* tmp2 = ini();
    tmp2->p = x;
    tmp2->nxt = p[y].nxt;
    p[x].nxt = tmp1;
    p[y].nxt = tmp2;
    return ;
}

void dfs1(int x,int f)
{
    fa[x] = f;
    dep[x] = dep[f]+1;
    tot[x] = 1;
    son[x] = 0;

    struct Node* tmp = p[x].nxt;
    int maxson=0;

    while (tmp != NULL)
    {
        //printf ("%d",tmp->p);
        if (tmp->p == f)
        {
            tmp = tmp->nxt;
            continue;
        }
        dfs1(tmp->p,x);
        tot[x] += tot[tmp->p];
        if (tot[tmp->p] > maxson)
        {
            maxson = tot[tmp->p];
            son[x] = tmp->p;
        }
        tmp = tmp->nxt;
    }

    //printf ("\n");

    return ;
}

void dfs2(int x,int f)
{
    cnt++;
    idx[x] = cnt;
    a[cnt] = b[x];
    top[x] = f;
    //重链
    if (son[x] != 0)
    {
        dfs2(son[x],f);
    }
    //轻链
    struct Node* tmp = p[x].nxt;
    while (tmp != NULL)
    {
        if (tmp->p == fa[x] || tmp->p == son[x])
        {
            tmp = tmp->nxt;
            continue;
        }
        dfs2(tmp->p,tmp->p);
        tmp = tmp->nxt;
    }

    return ;
}

void opt1(int x,int y,int z)
{
    while (top[x] != top[y])
    {
        if (dep[top[x]] < dep[top[y]]) swap(x,y);
        add(1,1,n,idx[top[x]],idx[x],z);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x,y);
    add(1,1,n,idx[x],idx[y],z);
    return ;
}

long long opt2(int x,int y)
{
    long long res=0;
    while (top[x] != top[y])
    {
        if (dep[top[x]] < dep[top[y]]) swap(x,y);
        res += query(1,1,n,idx[top[x]],idx[x]);
        res %= mod;
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x,y);
    res += query(1,1,n,idx[x],idx[y]);
    return res%mod;
}

void opt3(int x,int z)
{
    add(1,1,n,idx[x],idx[x]+tot[x]-1,z);
    return ;
}

long long opt4(int x)
{
    return query(1,1,n,idx[x],idx[x]+tot[x]-1) % mod;
}

int main (void)
{
    scanf ("%d %d %d %d",&n,&m,&r,&mod);

    for (int i=1;i<=n;i++)
    {
        scanf ("%d",&b[i]);
        p[i].nxt = NULL;
        p[i].data = b[i];
    }

    for (int i=0;i<n-1;i++)
    {
        int x,y;
        scanf ("%d %d",&x,&y);
        add_edge(x,y);
    }

    dfs1(r,0);
    dfs2(r,r);
    Build(1,1,n);

    for (int i=0;i<m;i++)
    {
        int opt;
        scanf ("%d",&opt);
        if (opt == 1)
        {
            int x,y,z;
            scanf ("%d %d %d",&x,&y,&z);
            opt1(x,y,z);
        }
        else if (opt == 2)
        {
            int x,y;
            printf ("%lld\n",opt2(x,y));
        }
        else if (opt == 3)
        {
            int x,z;
            scanf ("%d %d",&x,&z);
            opt3(x,z);
        }
        else
        {
            int x;
            scanf ("%d",&x);
            printf ("%lld\n",opt4(x));
        }
    }

    return 0;
}