【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，我们只能这样暴力： - 在$u$和$v$里选一个深度较大的（LCA肯定不是它吧），向上走一步。 - 走到一起就求出LCA了。 现在有树剖的话我们就不用一个个跳了： 假设我们记录了$x$所在重链的顶端为$top[x]$，那么： - 如果$top[u]=top[v]$，也就是他们俩在同一条链上（任何两条重链不可能有同一个顶端）。显然深度较小的就是LCA。 - 否则，它们处在两条不同的重链上，也就有两个顶端，那么深度较大的那个顶端（记作$top[u]$）一定不是LCA，我们可以直接跳到$father[top[u]]$。 我们发现，我们每次直接跳过一条重链，根据性质四及其拓展，我们发现，这个过程是$log\ N$级别的！ 那么如何修改和查询呢？根据性质零，每条重链一定在新序列里是一个区间，那么每跳过一条就对它所对应区间进行修改、查询嘛！ 给大家一点时间鼓掌！啪啪啪啪啪啪 ## 第四步：那么怎么实现树链剖分呢？ 好的，我们总结一下： 首先我们需要第一遍DFS，求出： - ``father[x]``，$x$的父亲。 - ``dep[x]``，$x$的深度。 - ``size[x]``，$x$的子树大小。 - ``son[x]``，$x$的重儿子。 显然这时我们才刚刚找出重儿子和重链，自然没法构造DFS序（新序列）和``top[x]``。所以我们再进行一次DFS，这次DFS要第一个访问重儿子，并求出： - ``top[x]``，$x$所在重链的顶端节点。 - ``seg[x]``，$x$在新序列里的下标。这里取名叫``seg[ ]``是因为在这里用线段树维护新序列。 - ``rev[x]``，新序列中$x$对应的树中的节点的编号。显然``rev[seg[x]]=x``。其实可求可不求，你想把树的权值直接复制到新序列里也没问题。 好，两遍DFS之后我们已经完成转化了。 接下来初始化你想用的数据结构。 再之后就是查询/修改子树，查询/修改链。具体流程上面已经介绍了。 那么，树链剖分，就华丽丽的结束啦~ 接下来是重头戏了！下面隆重请出，P3384的标算！这里采用线段树维护新序列。 ```cpp #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