原题链接

题解

dalao‘s blog

我自己的认识请看代码区

code

#include<bits/stdc++.h>
using namespace std;
int n,Q,root,mod;

int bigson[100005];//和自己在同一条链上的儿子节点
vector<int> G[100005];
int sizes[100005];//主要是为了求子树大小，经过验证选择哪一个儿子节点作为和自己同一条链的要求是可以变的
int fa[100005];//只会在链的开端使用，从一个链跳到另一条链
int depth[100005]={0};//深度是为了在求lca
int id[100005]={0};//id是为了线段树操作，太神了，一个节点的子树内的节点一定是连续的，这样就能直接线段树操作了
int cnt=0;//标记新的id
int a[100005];
int top[100005];//一条链的开端，保证一条链上的新id是连续的，这样就又可以线段树操作了，太神了
int tree[400005];
int lazytag[400005];

void pushdown(int node,int l,int r)
{
    tree[node]+=lazytag[node]*(r-l+1);
    tree[node]%=mod;
    if(l!=r)
    {
        lazytag[node*2]+=lazytag[node];
        lazytag[node*2]%=mod;
        lazytag[node*2+1]+=lazytag[node];
        lazytag[node*2+1]%=mod;
    }
    lazytag[node]=0;
}

void update(int node,int l,int r,int x,int y,int val)
{
    if(lazytag[node]) pushdown(node,l,r);
    if(l>y||r<x) return;
    if(l>=x&&r<=y)
    {
        lazytag[node]+=val;
        lazytag[node]%=mod;
        pushdown(node,l,r);//为什么这里要pushdown，因为要求遍历到的区间都要有真值
        return;
    }

    int mid=(l+r)/2;
    update(node*2,l,mid,x,y,val);
    update(node*2+1,mid+1,r,x,y,val);
    tree[node]=(tree[node*2]+tree[node*2+1])%mod;
}


int query(int node,int l,int r,int x,int y)
{
    if(lazytag[node]) pushdown(node,l,r);
    if(l>y||r<x) return 0;
    if(l>=x&&r<=y)
    {
        return tree[node];
    }

    int mid=(l+r)/2;
    return (query(node*2,l,mid,x,y)+query(node*2+1,mid+1,r,x,y))%mod;
}
void dfs1(int now,int f)
{
    depth[now]=0;
    int maxson=0;
    sizes[now]=1;
    fa[now]=f;
    bigson[now]=0;
    for(auto next:G[now])
    {
        if(next==f) continue;
        dfs1(next,now);
        if(depth[next]>maxson)
        {
            maxson=depth[next];
            bigson[now]=next;
        }
        sizes[now]+=sizes[next];
    }
    depth[now]=maxson+1;
}

void dfs2(int now,int topf)
{
    id[now]=++cnt;
    top[now]=topf;
    if(!bigson[now]) return;
    dfs2(bigson[now],topf);
    for(auto next:G[now])
    {
        if(next==fa[now]||next==bigson[now]) continue;
        dfs2(next,next);
    }
}

void addPath(int x,int y,int v)
{
    while(top[x]!=top[y])
    {
        if(depth[top[x]]>depth[top[y]]) swap(x,y);
        update(1,1,n,id[top[x]],id[x],v);
        x=fa[top[x]];
    }
    if(depth[x]>depth[y]) swap(x,y);
    update(1,1,n,id[y],id[x],v);
}

int sumPath(int x,int y)
{
    int ans=0;
    while(top[x]!=top[y])
    {
        if(depth[top[x]]>depth[top[y]]) swap(x,y);
        ans+=query(1,1,n,id[top[x]],id[x]);
        ans%=mod;
        x=fa[top[x]];
    }
    if(depth[x]>depth[y])  swap(x,y);
    ans+=query(1,1,n,id[y],id[x]);
    ans%=mod;
    return ans;
}




int main()
{
    cin>>n>>Q>>root>>mod;

    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }

    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    dfs1(root,0);
    dfs2(root,root);

    for(int i=1;i<=n;i++) update(1,1,n,id[i],id[i],a[i]);


    while(Q--)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            int x,y,v;
            cin>>x>>y>>v;
            v%=mod;
            addPath(x,y,v);
        }
        else if(op==2)
        {
            int x,y;
            cin>>x>>y;
            cout<<sumPath(x,y)<<endl;
        }
        else if(op==3)
        {
            int x,v;
            cin>>x>>v;
            v%=mod;
            update(1,1,n,id[x],id[x]+sizes[x]-1,v);
        }
        else
        {
            int x;
            cin>>x;
            cout<<query(1,1,n,id[x],id[x]+sizes[x]-1)<<endl;
        }
    }
    return 0;
}