树链剖分学习笔记

#include<bits/stdc++.h>
#define debug printf("!");
using namespace std;
typedef long long ll;
const int maxn=2e5+50;

vector<int>p[maxn];
int val[maxn],mod;


int siz[maxn],dep[maxn],fad[maxn],son[maxn];
int top[maxn],tid[maxn],rnk[maxn],cnt;
/*
siz[i] 保存以i为根的树的大小
dep[i]  i节点的深度
fad[i]  i的父亲
son[i]  i的重儿子
top[i]  重链的顶端节点
tid[i]  i的新编号(dfs) 
rnk[i]  rnk[tid[i]]=i
*/
inline void dfs1(int u,int fa,int d)
{
    /*
    u  当前节点 
    fa  父亲 
    d  深度 
    */
    dep[u]=d;
    fad[u]=fa;
    siz[u]=1;
    
    for(int i=0;i<p[u].size();i++)
    {
        int v=p[u][i];
        if(v==fa)continue;
        dfs1(v,u,d+1);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}

inline void dfs2(int u,int t)
{
    /*
    u  当前节点 
    t  顶端重节点 
    */
    top[u]=t;
    tid[u]=++cnt;
    rnk[cnt]=u; 
    if(!son[u])return;//当前节点不在重链上
    dfs2(son[u],t);
    for(int i=0;i<p[u].size();i++)
    {
        int v=p[u][i];
        if(v!=son[u]&&v!=fad[u])dfs2(v,v);//非重节点的top是自己 
    }
}

struct kkk{
    int l,r;ll sum,la;
}tree[maxn<<2];

inline void build(int k,int l,int r)
{
    tree[k].l=l;tree[k].r=r;
    if(l==r)
    {
        tree[k].sum=val[rnk[l]]%mod;
        return;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    tree[k].sum=(tree[k<<1].sum+tree[k<<1|1].sum)%mod;
}
inline void down(int k)
{
    tree[k<<1].sum=(tree[k<<1].sum+(tree[k<<1].r-tree[k<<1].l+1)*tree[k].la)%mod;
    tree[k<<1|1].sum=(tree[k<<1|1].sum+(tree[k<<1|1].r-tree[k<<1|1].l+1)*tree[k].la)%mod;
    tree[k<<1].la=(tree[k<<1].la+tree[k].la)%mod;
    tree[k<<1|1].la=(tree[k<<1|1].la+tree[k].la)%mod;
    tree[k].la=0;
}
inline void add(int k,int l,int r,ll w)
{
    if(l<=tree[k].l&&tree[k].r<=r)
    {
        tree[k].la=(tree[k].la+w)%mod;
        tree[k].sum=(tree[k].sum+(tree[k].r-tree[k].l+1)*w)%mod;
        return;
    }
    if(tree[k].la)down(k);
    int mid=(tree[k].l+tree[k].r)>>1;
    if(l<=mid)add(k<<1,l,r,w);
    if(r>mid)add(k<<1|1,l,r,w);
    tree[k].sum=(tree[k<<1].sum+tree[k<<1|1].sum)%mod;
}
inline int query(int k,int l,int r)
{
    if(l<=tree[k].l&&tree[k].r<=r)return tree[k].sum;
    if(tree[k].la)down(k);
    int mid=(tree[k].l+tree[k].r)>>1;
    ll ans=0;
    if(l<=mid)ans=(ans+query(k<<1,l,r))%mod;
    if(r>mid)ans=(ans+query(k<<1|1,l,r))%mod;
    return ans;
}
inline void addline(int x,int y,ll w)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        add(1,tid[top[x]],tid[x],w);
        x=fad[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    add(1,tid[x],tid[y],w);
}
inline int calline(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,tid[top[x]],tid[x]))%mod;
        x=fad[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    ans=(ans+query(1,tid[x],tid[y]))%mod;
    return ans;
}

int main()
{
    int n,m,G,i,u,v,w,op;
    scanf("%d%d%d%d",&n,&m,&G,&mod);
    for(i=1;i<=n;i++)scanf("%d",&val[i]);
    for(i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        p[u].push_back(v);
        p[v].push_back(u);
    }
//    memset(siz,0,sizeof(siz));
    memset(son,0,sizeof(son));
    dfs1(G,0,1);
    dfs2(G,G);
    build(1,1,n);
    while(m--)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%d",&u,&v,&w);
            addline(u,v,w%mod);
        }
        else if(op==2)
        {
            scanf("%d%d",&u,&v);
            printf("%d\n",calline(u,v)%mod);
        }
        else if(op==3)
        {
            scanf("%d%d",&u,&w);
            add(1,tid[u],tid[u]+siz[u]-1,w%mod);
        }
        else if(op==4)
        {
            scanf("%d",&u);
            printf("%d\n",query(1,tid[u],tid[u]+siz[u]-1)%mod);
        }
    }
}