10pts 求调

记录，RE on #6 and AC on #11，其余 TLE。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128
#define ull unsigned int
#define pb push_back
#define pii pair<int,int>
#define p3i pair<int,pii>
#define uset unordered_set
#define umap unordered_map
#define prq priority_queue
#define fi first
#define se second
#define ctn continue
#define N 100005
int n,T,rt,mod,a[N];
vector<int>e[N];
struct heavy_path_decomposition //重链剖分 
{
    //decomposition (n.) 分解 
    int tot=0,dep[N],fa[N],siz[N],son[N],dfn[N],rnk[N],top[N];
    void dfs1(int u)
    {
        dep[u]=dep[fa[u]]+1;
        siz[u]=1;
        for(int v:e[u])
        {
            if(v^fa[u])
            {
                fa[v]=u;
                dfs1(v);
                siz[u]+=siz[v];
                if(!son[u] || siz[v]>siz[son[u]])
                {
                    son[u]=v;
                }
            }
        }
    }
    void dfs2(int u,int t)
    {
        dfn[u]=++tot;
        rnk[tot]=u;
        top[u]=t;
//      cout<<"u="<<u<<"  t="<<t<<"  tot="<<tot<<"  dfn[u]="<<dfn[u]<<"  rnk[tot]="<<rnk[tot]<<"  top[u]="<<top[u]<<"\n";
        if(!son[u])
        {
            return;
        }
        dfs2(son[u],t);
        for(int v:e[u])
        {
            if(v^fa[u] && v^son[u])
            {
                dfs2(v,v);
            }
        }
    }
    int lca(int x,int y)
    {
        while(top[x]^top[y])
        {
            if(dep[top[x]]<dep[top[y]])
            {
                swap(x,y);
            }
            x=fa[top[x]];
        }
        return dep[x]<dep[y] ? x : y;
    }
}hpd;
struct segment_tree //线段树 
{
    struct node
    {
        int l,r,val,tag;
        node(int _l=0,int _r=0,int _val=0,int _tag=0)
        {
            l=_l, r=_r, val=_val, tag=_tag;
        }
    }t[N<<2];
    void build(int p,int l,int r)
    {
        if(l==r)
        {
            t[p]=node(l,r,a[hpd.rnk[l]]%mod,0);
//          cout<<"t["<<p<<"]={"<<l<<","<<r<<","<<a[hpd.rnk[l]]%mod<<",0}\n";
            return;
        }
        int mid=(l+r)>>1;
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
        t[p]=node(l, r, (t[p<<1].val+t[p<<1|1].val)%mod, 0);
    }
    void push_down(int p)
    {
        if(t[p].tag)
        {
            t[p<<1].tag+=t[p].tag;
            t[p<<1].tag%=mod;
            t[p<<1].val+=(t[p<<1].r-t[p<<1].l+1)*t[p].tag;
            t[p<<1].val%=mod;
            t[p<<1|1].tag+=t[p].tag;
            t[p<<1|1].tag%=mod;
            t[p<<1|1].val+=(t[p<<1|1].r-t[p<<1|1].l+1)*t[p].tag;
            t[p<<1|1].val%=mod;
            t[p].tag=0;
        }
    }
    int query(int p,int l,int r)
    {
        if(t[p].r<l || t[p].l>r)
        {
            return 0;
        }
        if(t[p].l>=l && t[p].r<=r)
        {
            return t[p].val%mod;
        }
        push_down(p);
        return ( query(p<<1,l,r) + query(p<<1|1,l,r) ) % mod;
    }
    void add(int p,int l,int r,int k)
    {
        int pl=t[p].l, pr=t[p].r;
        if(pr<l || pl>r)
        {
            return;
        }
        t[p].val+=(min(pr,r)-max(pl,l)+1)*k;
        t[p].val%=mod;
        if(pl>=l && pr<=r)
        {
            t[p].tag+=k;
            t[p].tag%=mod;
            return;
        }
        push_down(p);
        add(p<<1,l,r,k);
        add(p<<1|1,l,r,k);
    }
}seg;
int add_path(int x,int y,int z)
{
    z%=mod;
//  cout<<"x="<<x<<"  y="<<y<<"  top[x]="<<hpd.top[x]<<"  top[y]="<<hpd.top[y]<<"\n";
    while(hpd.top[x]^hpd.top[y])
    {
//      cout<<"(top[x] != top[y])  x="<<x<<"  y="<<y<<"  top[x]="<<hpd.top[x]<<"  top[y]="<<hpd.top[y]<<"\n";
        if(hpd.dep[ hpd.top[x] ] < hpd.dep[ hpd.top[y] ])
        {
            swap(x,y);
        }
        seg.add(1, hpd.dfn[ hpd.top[x] ], hpd.dfn[x], z);
//      cout<<"add(1,"<<hpd.dfn[ hpd.top[x] ]<<","<<hpd.dfn[x]<<","<<z<<")\n";
        x = hpd.fa[ hpd.top[x] ];
    }
    if(hpd.dep[x] > hpd.dep[y])
    {
        swap(x,y);
    }
    seg.add(1, hpd.dfn[x], hpd.dfn[y], z);
}
int query_path(int x,int y)
{
    int ret=0;
    while(hpd.top[x]^hpd.top[y])
    {
        if(hpd.dep[ hpd.top[x] ] < hpd.dep[ hpd.top[y] ])
        {
            swap(x,y);
        }
        ret+=seg.query(1, hpd.dfn[ hpd.top[x] ], hpd.dfn[x]);
        ret%=mod;
        x = hpd.fa[ hpd.top[x] ];
    }
    if(hpd.dep[x] > hpd.dep[y])
    {
        swap(x,y);
    }
    ret+=seg.query(1, hpd.dfn[x], hpd.dfn[y]);
    ret%=mod;
    return ret;
}
signed main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
//  ios::sync_with_stdio(0);
//  cin.tie(0);
//  cout.tie(0);
    cin>>n>>T>>rt>>mod;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1,u,v;i<n;i++)
    {
        cin>>u>>v;
        e[u].pb(v);
        e[v].pb(u);
    }
    hpd.dfs1(rt);
    hpd.dfs2(rt,rt);
    seg.build(1,1,n);
    while(T--)
    {
        int op,x,y,z;
        cin>>op>>x;
        if(op==1)
        {
            cin>>y>>z;
            z=(z%mod+mod)%mod;
            add_path(x,y,z);
        }
        else if(op==2)
        {
            cin>>y;
            cout<<query_path(x,y)<<"\n";
        }
        else if(op==3)
        {
            cin>>z;
            z=(z%mod+mod)%mod;
            seg.add(1, hpd.dfn[x], hpd.dfn[x]+hpd.siz[x]-1, z);
        }
        else
        {
            cout<<seg.query(1, hpd.dfn[x], hpd.dfn[x]+hpd.siz[x]-1)<<"\n";
        }
    }
    return 0;
}