树链剖分

树链剖分有什么用

我们经常会写到这样的毒瘤题目：给你一棵树，每次对树上的一条链进行操作。  

例如洛咕：P3384 【模板】树链剖分。

实现方法

那么我们怎么很快的处理这样的问题呢？

学过倍增LCA的同学应该清楚，就算是倍增，也只能找出它的几代父亲，而不能对路径上的每一个点进行修改。

我们发现对于树上链的操作是很复杂的，因为树上的节点储存是不连续的。

然后你就能拍脑袋了。

既然不连续的区间修改起来很麻烦，那么有没有方法把它变成连续的呢？

我们发现对于一棵树，我们对节点的储存顺序是没有要求的。

对于一个父节点，我们只需要知道他儿子们的储存位置；对于一个子节点，我们只要知道他父亲的储存位置，我们就可以存储这棵树了。

那么我们可以通过给这棵树进行重标号，把树上的链化为连续的区间，我们就能很轻松地处理一段链的修改，查询操作了。

下面有几个定义：

1.重儿子：一个节点的儿子节点里面，以重儿子为根的子树大小最大。

2.轻儿子：一个节点的儿子节点，除了唯一一个重儿子，其余儿子为轻儿子。

3.重边：连接父亲和重儿子的边称为重边。

4.轻边：连接父亲和轻儿子的边称为轻边。

5.重链：只由重边构成的链称为重链。

我们只要把一棵树上的重链全部按顺序储存，就能把树上的问题转化为区间上的问题。

那么接下来用线段树就能轻松维护这个区间问题了。

时间复杂度证明

我们已经学会给树解剖了（雾）

那么我们怎么知道按照重链解剖，时间复杂度会变得更优呢？

1.每走过一个轻边，子树的节点数至少减少一半

我们假设树上一个节点有$n$个儿子，那么由于重儿子子树大小是最大的，当轻儿子的子树大小最大的时候，轻儿子的子树大小应该为frac{1}{n}$。

我们可以用抽屉原理证明。

那么轻儿子子树大小之多为父亲的$frac{1}{2}$

2.一条链上最多有$2logn$条重链

 这个也是很好证明的。（虽然是伪证）

我们考虑什么时候链最多。

我们先考虑半链。

发现重链的数量只和轻边有关。

因为重链的两端所连的节点不可能再连接其他的重边，不然长度就会增加。

那么一段链上的重链数就等于轻边数$+1$。

根据结论$1$，一个节点数为$n$的树，最多走$logn$次轻边，节点数就会变成$1$。

换句话说，一条半链上最多有$logn$条轻边。

那么一条全链上最多有$2logn$条重链。

3.单次修改，查询的操作为$log^2n$

我们每次查询可以修改一条链从链底到链顶的一段区间。

根据结论$2$我们知道，单次修改的线段树操作次数为$logn$次，而线段树的时间复杂度为$logn$。

总的时间复杂度就是$log^2n$

具体的实现细节

我们先对树进行预处理，把树重标号以及剖分出重链。

这个预处理由两个dfs构成。

第一个dfs，我们可以计算出以下几个值。

1.每个节点的子树大小$siz[x]$

2.每个节点的深度$dep[x]$

3.每个节点的父亲$fa[x]$

4.每个节点的重儿子$son[x]$

void dfs1(int x,int pre,int deep){
    dep[x]=deep;siz[x]=1;
    for(int i=head[x];i;i=nxt[i]){
        if(ver[i]==pre)continue;
        fa[ver[i]]=x;
        dfs1(ver[i],x,deep+1);
        siz[x]+=siz[ver[i]];
        if(siz[son[x]]<siz[ver[i]])son[x]=ver[i];
    }
}

 然后第二个dfs，我们给每个节点重新标号。

统计出以下数组。

1.每个节点在线段树上的位置$id[x]$

2.线段树某个位置上的权值$rw[x]$

3.每个节点所在链的链顶节点$top[x]$

为了保证重链上的点储存位置连续，我们要先对重链进行标号。

void dfs2(int x,int ltp){
    id[x]=++cnt;
    a[cnt]=w[x];
    top[x]=ltp;
    if(son[x])dfs2(son[x],ltp);
    for(int i=head[x];i;i=nxt[i]){
        if(ver[i]==son[x]||ver[i]==fa[x])continue;
        dfs2(ver[i],ver[i]);
    }
}

可能比较抽象，我们可以通过一张图来看。

红色框住的为重链，黑色标号为原来的编号，棕色标号为线段树位置。

我们很容易发现重链上的节点是连续的，子树内的节点是连续的。

那么我们就很容易进行维护了。

至于线段树部分，就不详细解释了。直接看代码就好了

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+100;
int read(){
    char c;int num,f=1;
    while(c=getchar(),!isdigit(c))if(c=='-')f=-1;num=c-'0';
    while(c=getchar(), isdigit(c))num=num*10+c-'0';
    return f*num;
}
int mod=1e9+7;
int n,m,r,p;
int w[N],dep[N],fa[N],son[N],id[N],top[N];
int head[N],nxt[N*2],ver[N*2],tot=1,siz[N],cnt=0;
void up(int &x,int y){
    x+=y;
    if(x>=mod)x-=mod;
}
//线段树
int laz[N*4],tree[N*4],a[N];
/*void build(int l,int r,int rt){
    for(int i=1;i<=n;i++)tree[i]=a[i];
}
void modify(int l,int r,int L,int R,int rt,int x){
    for(int i=L;i<=R;i++)up(tree[i],x);
}
int query(int l,int r,int L,int R,int rt){
    int ans=0;
    for(int i=L;i<=R;i++)up(ans,tree[i]);
    return ans;
}*/

void update(int rt){
    tree[rt]=tree[rt<<1]+tree[rt<<1|1];
    if(tree[rt]>=mod)tree[rt]-=mod;
}
void build(int l,int r,int rt){
    if(l==r){tree[rt]=a[l]%mod;return ;}
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    update(rt);
}
void pushdown(int rt,int len){
    up(laz[rt<<1],laz[rt]);
    up(tree[rt<<1],laz[rt]*(len-(len>>1))%mod);
    up(laz[rt<<1|1],laz[rt]);
    up(tree[rt<<1|1],laz[rt]*(len>>1)%mod);
    laz[rt]=0;
}
int query(int l,int r,int L,int R,int rt){
    if(L<=l&&r<=R)return tree[rt];
    int mid=(l+r)>>1,ans=0;
    pushdown(rt,r-l+1);
    if(L<=mid)up(ans,query(l,mid,L,R,rt<<1));
    if(mid+1<=R)up(ans,query(mid+1,r,L,R,rt<<1|1));
    return ans;
}
void modify(int l,int r,int L,int R,int rt,int x){
    if(L<=l&&r<=R){
        up(tree[rt],x*(r-l+1)%mod);
        up(laz[rt],x);
        return ;
    }
    int mid=(l+r)>>1;
    pushdown(rt,r-l+1);
    if(L<=mid)modify(l,mid,L,R,rt<<1,x);
    if(mid+1<=R)modify(mid+1,r,L,R,rt<<1|1,x);
    update(rt);
}


void add_edge(int u,int v){
    ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;
    ver[++tot]=u;nxt[tot]=head[v];head[v]=tot;
}
void dfs1(int x,int pre,int deep){
    dep[x]=deep;siz[x]=1;
    for(int i=head[x];i;i=nxt[i]){
        if(ver[i]==pre)continue;
        fa[ver[i]]=x;
        dfs1(ver[i],x,deep+1);
        siz[x]+=siz[ver[i]];
        if(siz[son[x]]<siz[ver[i]])son[x]=ver[i];
    }
}
void dfs2(int x,int ltp){
    id[x]=++cnt;
    a[cnt]=w[x];
    top[x]=ltp;
    if(son[x])dfs2(son[x],ltp);
    for(int i=head[x];i;i=nxt[i]){
        if(ver[i]==son[x]||ver[i]==fa[x])continue;
        dfs2(ver[i],ver[i]);
    }
}
void link_modify(int x,int y,int val){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        modify(1,n,id[top[x]],id[x],1,val);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])swap(x,y);
    modify(1,n,id[y],id[x],1,val);
}
int link_query(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        up(ans,query(1,n,id[top[x]],id[x],1));
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])swap(x,y);
    up(ans,query(1,n,id[y],id[x],1));
    return ans;
}
void tree_modify(int x,int val){
    modify(1,n,id[x],id[x]+siz[x]-1,1,val%mod);
}
int tree_query(int x){
    return query(1,n,id[x],id[x]+siz[x]-1,1);
}
int main()
{
    //freopen("data.in","r",stdin);
    n=read();m=read();
    r=read();mod=read();
    for(int i=1;i<=n;i++)w[i]=read();
    for(int i=1;i< n;i++)add_edge(read(),read());
    dfs1(r,r,1);dfs2(r,r);build(1,n,1);
    for(int i=1;i<=m;i++){
        int opt=read(),x,y,z;
        if(opt==1){
            x=read();y=read();z=read();
            link_modify(x,y,z);
        }else if(opt==2){
            x=read();y=read();
            printf("%d
",link_query(x,y));
        }else if(opt==3){
            x=read();y=read();
            tree_modify(x,y);
        }else if(opt==4){
            x=read();
            printf("%d
",tree_query(x));
        }
    }
    //cout<<siz[1]<<endl;
    /*for(int i=1;i<=10;i++)a[i]=i;
    build(1,10,1);
    modify(1,10,1,10,1,10);
    cout<<query(1,10,1,3,1)<<endl;
    modify(1,10,2,9,1,10);
    cout<<query(1,10,1,3,1)<<endl;
    modify(1,10,1,2,1,10);
    cout<<query(1,10,1,3,1)<<endl;*/
    return 0;
}