树链剖分

题目链接： https://www.luogu.org/problemnew/show/P3384

感觉洛谷的树剖模板出的挺好的，涉及的面比一些省选题要多得多。

树链剖分

众所周知，对树上两个不相邻节点的操作，若转化为链上的操作，则会方便许多。

顾名思义，树链剖分就是把 一棵树分成几条链，把树形变为线性，减少处理难度。

需要提前掌握的知识：, 树形, 树的序, 线段树。

需要知道的概念：

• 重儿子：对于每一个非叶子节点，它的儿子中 儿子数量最多的那一个儿子 为该节点的重儿子
• 轻儿子：对于每一个非叶子节点，它的儿子中 非重儿子 的剩下所有儿子即为轻儿子
• 叶子节点没有重儿子也没有轻儿子（因为它没有儿子。。）
• 重边：连接任意两个重儿子的边叫做重边
• 轻边：剩下的即为轻边
• 重链：相邻重边连起来的 连接一条重儿子 的链叫重链
• 对于叶子节点，若其为轻儿子，则有一条以自己为起点的长度为1的链
• 每一条重链以轻儿子为起点

树剖分为一些部分：

• 1.深搜处理出每个点的深度，父亲节点，包括它自己的子树节点大小，和重儿子的编号。
• 2.深搜处理出每个点在新链上的编号，以及链顶的编号。
• 3.建一颗线段树，来进行区间的操作。

dfs1

void dfs1(int x,int last,int depth)
{
    father[x]=last;
    dep[x]=depth;
    sonnum[x]=1;
    int maxnum=-1;
    for(int i=head[x];i;i=edge[i].nextt)
    {
        int to=edge[i].to;
        if(to==last) continue;
        dfs1(to,x,depth+1);
        sonnum[x]+=sonnum[to];
        if(sonnum[to]>maxnum) maxnum=sonnum[to],son[x]=to;
    }
}

应该比较好理解。。。

dfs2

void dfs2(int x,int topx)
{
    ncnt[x]=++cnt;
    nval[cnt]=val[x]%mod;
    top[x]=topx;
    if(!son[x]) return ;
    dfs2(son[x],topx);
    for(int i=head[x];i;i=edge[i].nextt)
    {
        int to=edge[i].to;
        if(to==father[x]||to==son[x]) continue;
        dfs2(to,to);
    }
}

要先处理重儿子，因为要保证是一条编号连续的重链。

要处理的一些问题

• 处理任意两点间路径上的点权和
• 处理一点及其子树的点权和
• 修改任意两点间路径上的点权
• 修改一点及其子树的点权

处理任意两点间路径上的点权和

inline int qRange(int x,int y)
{
    int ans=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        ans=(ans%mod+Tree.query(1,1,n,ncnt[top[x]],ncnt[x])%mod)%mod;
        x=father[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    ans=(ans%mod+Tree.query(1,1,n,ncnt[x],ncnt[y])%mod)%mod;
    return ans%mod;
}

就是按深度，像一样，选取一个低的点往上跳，对树上的区间依次操作。

处理一点及其子树的点权和

printf("%d\n",Tree.query(1,1,n,ncnt[x],ncnt[x]+sonnum[x]-1)%mod);

先前统计出了子树大小，因为编号连续，所以直接查询连续区间即可。

修改任意两点间路径上的点权

inline void updRange(int x,int y,int z)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        Tree.update(1,1,n,ncnt[top[x]],ncnt[x],z);
        x=father[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    Tree.update(1,1,n,ncnt[x],ncnt[y],z);
}

原理与上面查询类似。

修改一点及其子树的点权

Tree.update(1,1,n,ncnt[x],ncnt[x]+sonnum[x]-1,z%mod);

就。。没什么了

全部代码：

#include <cstdio>
#include <cctype>
#include <cstring> 
#include <iostream>
#define ls p<<1
#define rs p<<1|1
static const int MAXN=200050; 
using namespace std;
struct Edge
{
    int to,nextt;
}edge[MAXN];
int n,m,r,mod,ins,u,v,x,y,z,cnt,num,head[MAXN],val[MAXN],top[MAXN],ncnt[MAXN],nval[MAXN],dep[MAXN],sonnum[MAXN],son[MAXN],father[MAXN];
inline int read()
{
    int x=0;bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
int a[MAXN<<2],tag[MAXN<<2];
struct Segment_Tree
{
    inline void push_up(int p){a[p]=(a[ls]+a[rs])%mod;}
    inline void push_down(int p,int l,int r,int mid)
    {
        tag[ls]+=tag[p];
        tag[rs]+=tag[p];
        a[ls]+=((mid-l+1)*tag[p])%mod;
        a[rs]+=((r-mid)*tag[p])%mod;
        tag[p]=0;
    }
    void build(int p,int l,int r)
    {
        if(l==r)
        {
            a[p]=nval[l]%mod;
            return ;
        }
        int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        push_up(p);
    }
    void update(int p,int l,int r,int ql,int qr,int z)
    {
        if(ql<=l&&qr>=r)
        {
            a[p]+=((r-l+1)*z)%mod;
            tag[p]+=z;
            return ;
        }
        int mid=(l+r)>>1;
        if(tag[p]) push_down(p,l,r,mid);
        if(ql<=mid) update(ls,l,mid,ql,qr,z);
        if(qr>mid) update(rs,mid+1,r,ql,qr,z);
        push_up(p);
    }
    int query(int p,int l,int r,int ql,int qr)
    {
        if(ql<=l&&qr>=r) return a[p]%mod;
        int mid=(l+r)>>1,sum=0;
        if(tag[p]) push_down(p,l,r,mid);
        if(ql<=mid) sum+=query(ls,l,mid,ql,qr);
        if(qr>mid) sum+=query(rs,mid+1,r,ql,qr);
        push_up(p);
        return sum%mod;
    }
}Tree;
inline void addedge(int u,int v)
{
    edge[++num].to=v;
    edge[num].nextt=head[u];
    head[u]=num;
}
void dfs1(int x,int last,int depth)
{
    father[x]=last;
    dep[x]=depth;
    sonnum[x]=1;
    int maxnum=-1;
    for(int i=head[x];i;i=edge[i].nextt)
    {
        int to=edge[i].to;
        if(to==last) continue;
        dfs1(to,x,depth+1);
        sonnum[x]+=sonnum[to];
        if(sonnum[to]>maxnum) maxnum=sonnum[to],son[x]=to;
    }
}
void dfs2(int x,int topx)
{
    ncnt[x]=++cnt;
    nval[cnt]=val[x]%mod;
    top[x]=topx;
    if(!son[x]) return ;
    dfs2(son[x],topx);
    for(int i=head[x];i;i=edge[i].nextt)
    {
        int to=edge[i].to;
        if(to==father[x]||to==son[x]) continue;
        dfs2(to,to);
    }
}
inline void updRange(int x,int y,int z)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        Tree.update(1,1,n,ncnt[top[x]],ncnt[x],z);
        x=father[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    Tree.update(1,1,n,ncnt[x],ncnt[y],z);
}
inline int qRange(int x,int y)
{
    int ans=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        ans=(ans%mod+Tree.query(1,1,n,ncnt[top[x]],ncnt[x])%mod)%mod;
        x=father[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    ans=(ans%mod+Tree.query(1,1,n,ncnt[x],ncnt[y])%mod)%mod;
    return ans%mod;
}
int main()
{
    n=read();m=read();
    r=read();mod=read();
    for(int i=1;i<=n;i++) val[i]=read();
    for(int i=1;i<=n-1;i++)
    {
        u=read();v=read();
        addedge(u,v);
        addedge(v,u);
    }
    dfs1(r,0,1);
    dfs2(r,r); 
    Tree.build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        ins=read();
        if(ins==1)
        {
            x=read();y=read();z=read();
            updRange(x,y,z%mod);
        } 
        else if(ins==2)
        {
            x=read();y=read();
            printf("%d\n",qRange(x,y)%mod);
        }
        else if(ins==3)
        {
            x=read();z=read();
            Tree.update(1,1,n,ncnt[x],ncnt[x]+sonnum[x]-1,z%mod);
        }
        else
        {
            x=read();
            printf("%d\n",Tree.query(1,1,n,ncnt[x],ncnt[x]+sonnum[x]-1)%mod);
        }
    }
    return 0;
}