【x义x讲坛】dfs序与树链剖分入门

· · 个人记录

对我又是刚学完某算法又直接写博客了……

关于树链剖分，我刚开始听到这个名字的时候是拒绝的：

哇这个算法一定很高级，吾等pj蒟蒻还是退避吧

看到百度百科的定义：树链剖分，计算机术语，指一种对树进行划分的算法，它先通过轻重边剖分将树分为多条链，保证每个点属于且只属于一条链，然后再通过数据结构（树状数组、SBT、SPLAY、线段树等）来维护每一条链。

我直接就跑了……

然而，学了这玩意之后，额貌似也没那么难嘛。

考虑到网上那些扔了定义扔了标程就跑的材料，机房众dalao对我“树链剖分很水”的观点的迷茫的眼神，今天，我就先简单讲讲树链剖分。

（提醒：严格来讲这篇博客讲的是重链剖分）

第一步：你需要弄懂什么是DFS序

树链剖分在某种意义上可以直接认为是正常的DFS序加上一个限制，从而使得新序列具有一些神奇的性质。至于什么限制，什么性质，此处不表。

所以我们还是一定要弄懂DFS序。

DFS序呢，简单来说，就是把一个树重构成一个序列。我们现在用下面这棵树来介绍一下这是个什么过程。

我们从根节点开始DFS（这里约定从左到右访问子节点），每到一个节点就给它标上一个时间戳seg[\ ]，同时要维护好每个节点的子树大小size[\ ]。这里并不模拟整个标记过程了，DFS相信来看这篇博客的人都会。

现在我们按时间戳把这个树弄成序列。

（左上的\color{red}\text{小红}数字表示时间戳。子树大小不放了）

（方框们上方的\color{red}\text{小红}数字是下标，也是时间戳。方框里的是元素，也就是树中的节点编号。）

（请您将这幅图再看几遍，已确定您搞懂了：\color{red}\text{小红}数字是树中的时间戳，是新序列中的下表；黑数字是树中的节点编号，是新序列的元素）

观察一下：

由于我们在对于一个节点的子树进行遍历的时候，只要不遍历结束就不会离开这个子树，所以一个节点的子树的时间戳一定是连续的！对应在新序列里就是一段区间！

比如树中节点3的子树就是\{ 3,6,7,10,11\} ，反映在新序列里就是区间[4,8]。

那么对一个节点的子树进行操作、询问就是对新序列里的一段区间[seg[x],seg[x]+size[x]-1]操作、询问。区间操作、询问令你想到了什么呢？

要么线段树要么树状数组嘛~个别毒瘤题甚至需要其他数据结构，此处不表。

给大家一段时间鼓掌！啪啪啪啪啪啪

模板题：P2982，P3605。 思路都是对节点按权值排序，然后查询我的子树（那个区间）中有几个比我小的，然后再原地+1。

标程为节省博客长度，此处不表。再说树链剖分作为DFS序的扩展可以解决一切DFS序问题，要的话自己看树链剖分标程吧。

第二步：那么什么是树链剖分呢

还记得我在开头说过：

树链剖分在某种意义上可以直接认为是正常的DFS序加上一个限制，从而使得新序列具有一些神奇的性质。

好，那么答案揭晓：这个限制就是“必须先访问我的size[\ ]最大的儿子”。如果多个儿子size[\ ]都最大那么随便选一个。

我们把“size[\ ]最大的儿子”叫做重儿子，连接父亲和重儿子的边叫做重边，一串首尾相接的重边叫做重链。

我个人同时约定如果是叶子节点，那么也算有一条不指向任何东西的重边。（方便您理解性质一QAQ）

（画蓝的边表示重边）

【性质零】一条重链在新序列里一定是连续的一条。
【性质一】每个节点一定在且仅在一条重链上。

如果是轻儿子，那么一定是一条重链的顶端；如果是重儿子，那么一定是在一条重链的中间。

【性质二】如果(u,v)为轻边，则size[v]\le size[u]。

就算u只有两个儿子，就算那个重儿子的size[\ ]=size[v]，那也只能取到等号啊。

【性质三】从根到u的路径上的轻边数不多于log\ N。

每经过一条轻边，size[\ ]就至少减半。就算u是叶子节点，当size[\ ]=1的时候也肯定找到了。

同理任何两点之间的路径上的轻边不多于2log\ N。

【性质四】从根到u的路径上的重链数不多于log\ N+1。

重链是由轻边分隔的，所以也很明显吧。

同理任何两点之间的路径上的重链不多于2log\ N+2。

那么这些性质有什么用呢？

注意到树链剖分就是DFS序的扩展，DFS序能干的东西它都能一样干。如果对一个节点的子树进行修改、查询？如果你忘了请翻到第一步回忆一下。

可是，如果我想对(u,v)之间的这条链进行修改、查询呢？

第三步：如何用树剖对一条链(u,v)进行修改和查询

假如我们没有树剖，没有ST表，啥东西都没有，那么我们如果想求(u,v)的LCA，我们只能这样暴力：

现在有树剖的话我们就不用一个个跳了：

假设我们记录了x所在重链的顶端为top[x]，那么：

我们发现，我们每次直接跳过一条重链，根据性质四及其拓展，我们发现，这个过程是log\ N级别的！

那么如何修改和查询呢？根据性质零，每条重链一定在新序列里是一个区间，那么每跳过一条就对它所对应区间进行修改、查询嘛！

给大家一点时间鼓掌！啪啪啪啪啪啪

第四步：那么怎么实现树链剖分呢？

好的，我们总结一下：

首先我们需要第一遍DFS，求出：

显然这时我们才刚刚找出重儿子和重链，自然没法构造DFS序（新序列）和top[x]。所以我们再进行一次DFS，这次DFS要第一个访问重儿子，并求出：

好，两遍DFS之后我们已经完成转化了。

接下来初始化你想用的数据结构。

再之后就是查询/修改子树，查询/修改链。具体流程上面已经介绍了。

那么，树链剖分，就华丽丽的结束啦~

接下来是重头戏了！下面隆重请出，P3384的标算！这里采用线段树维护新序列。

#include<bits/stdc++.h>
using namespace std;

const int maxN=100005;
int N,Q,S,TT;
int A[maxN];

//前向星组件 
int lnk[maxN];
int pre[maxN*2],tgt[maxN*2],cnt;
void add_E(int u,int v){
    pre[++cnt]=lnk[u],tgt[cnt]=v,lnk[u]=cnt;
}

//树剖组件 
int father[maxN],dep[maxN],size[maxN],son[maxN];
int top[maxN],seg[maxN],idx,rev[maxN];

void DFS1(int x,int fa){
    size[x]=1;father[x]=fa;dep[x]=dep[fa]+1;
    for(int e=lnk[x];e;e=pre[e]){
        int v=tgt[e];
        if(v!=fa){
            DFS1(v,x);
            size[x]+=size[v];
            if(size[v]>size[son[x]]) son[x]=v;
        }
    }
}

void DFS2(int x,int fa){
    if(son[x]){
        seg[son[x]]=++idx;
        top[son[x]]=top[x];
        rev[idx]=son[x];
        DFS2(son[x],x);
    }
    for(int e=lnk[x];e;e=pre[e]){
        int v=tgt[e];
        if(v!=fa && v!=son[x]){
            seg[v]=++idx;
            top[v]=v;
            rev[idx]=v;
            DFS2(v,x);
        }
    }
}

//线段树
int sum[maxN<<2],lzy[maxN<<2];

void pushup(int x){
    sum[x]=(sum[x*2]+sum[x*2+1])%TT;
}
void pushdown(int x,int l,int r){
    int mid=(l+r)/2;
    sum[x*2]=(sum[x*2]+lzy[x]*(mid-l+1)%TT)%TT;
    sum[x*2+1]=(sum[x*2+1]+lzy[x]*(r-mid)%TT)%TT;
    lzy[x*2]=(lzy[x*2]+lzy[x])%TT;
    lzy[x*2+1]=(lzy[x*2+1]+lzy[x])%TT;
    lzy[x]=0;
}
void Build(int x,int l,int r){
    if(l==r){sum[x]=A[rev[l]]%TT;return;}
    int mid=(l+r)/2;
    Build(x*2,l,mid);Build(x*2+1,mid+1,r);
    pushup(x);
}
void Update(int x,int l,int r,int L,int R,int k){
    int mid=(l+r)/2;
    if(L<=l && r<=R){
        sum[x]=(sum[x]+k*(r-l+1))%TT;lzy[x]=(lzy[x]+k)%TT;
        return;
    }
    pushdown(x,l,r);
    if(L<=mid) Update(x*2,l,mid,L,R,k);
    if(R>mid) Update(x*2+1,mid+1,r,L,R,k);
    pushup(x);
}
int Query(int x,int l,int r,int L,int R){
    int mid=(l+r)/2;
    if(L<=l && r<=R){return sum[x]%TT;}
    pushdown(x,l,r);pushup(x);
    int ans=0;
    if(L<=mid) ans=(ans+Query(x*2,l,mid,L,R))%TT;
    if(R>mid) ans=(ans+Query(x*2+1,mid+1,r,L,R))%TT;
    return ans;
} 

//终极实现
int Query_Chain(int u,int v){
    int ans=0;
    int fu=top[u],fv=top[v];
    while(fu!=fv){
        if(dep[fu]<dep[fv]) swap(u,v),swap(fu,fv);
        ans=(ans+Query(1,1,N,seg[fu],seg[u]))%TT;
        u=father[fu];fu=top[u];
    }
    if(dep[u]>dep[v]) swap(u,v);
    ans=(ans+Query(1,1,N,seg[u],seg[v]))%TT;
    return ans;
} 
void Update_Chain(int u,int v,int k){
    int fu=top[u],fv=top[v];
    while(fu!=fv){
        if(dep[fu]<dep[fv]) swap(u,v),swap(fu,fv);
        Update(1,1,N,seg[fu],seg[u],k);
        u=father[fu];fu=top[u];
    }
    if(dep[u]>dep[v]) swap(u,v);
    Update(1,1,N,seg[u],seg[v],k);
}

int Query_Subtree(int u){
    return Query(1,1,N,seg[u],seg[u]+size[u]-1);
}
void Update_Subtree(int u,int k){
    Update(1,1,N,seg[u],seg[u]+size[u]-1,k);
}

int main(){
    cin>>N>>Q>>S>>TT;
    for(int i=1;i<=N;i++) cin>>A[i];
    for(int i=1;i<=N-1;i++){
        int u,v;cin>>u>>v;add_E(u,v);add_E(v,u);
    }
    DFS1(S,0);idx=seg[S]=1;rev[1]=top[S]=S;DFS2(S,0);
    Build(1,1,N);
    for(int i=1;i<=Q;i++){
        int opr;cin>>opr;
        if(opr==1){
            int u,v,k;cin>>u>>v>>k;
            Update_Chain(u,v,k);
        }
        if(opr==2){
            int u,v;cin>>u>>v;
            cout<<Query_Chain(u,v)<<endl;
        }
        if(opr==3){
            int u,k;cin>>u>>k;
            Update_Subtree(u,k);
        }
        if(opr==4){
            int u;cin>>u;
            cout<<Query_Subtree(u)<<endl;
        }
    }
}

第五步：后记

标准的树剖其实也就那四个东西，没啥花样。那几道模板 （P3384，P2146，P3178，P2590） 也不一一讲了。树剖只是工具，最重要的还是如何建模，让问题变成标准的树剖。这才是最重要的东西。

所以，还是希望如果您有建议请及时反馈哦QWQ