企业官网建设流程全解析

引入

树链剖分，顾名思义，就是将一棵树剖成一条条链。这种算法可以帮助我们快速解决一类和树上路径有关的的问题。

P3384 【模板】重链剖分 / 树链剖分

给定一棵n nn个点的树，需要支持q qq次询问，分为如下几种：

• 1 x y z，表示将树从x xx到y yy结点最短路径上所有节点的值都加上z zz。
• 2 x y，表示求树从x xx到y yy结点最短路径上所有节点的值之和。
• 3 x z，表示将以x xx为根节点的子树内所有节点值都加上z zz。
• 4 x，表示求以x xx为根节点的子树内所有节点值之和。

n , q ≤ 10 5 n,q \le 10^5n,q≤105。

算法流程

既然知道了需要剖，那么怎么剖，以及剖好之后如何解决问题？下面我们详细说说。

怎么剖

首先看怎么剖。树剖有两种，一种是重链剖分，一种是长链剖分，后者用的比较少，这里我们讲前面这种。

对于树上每个点，我们记录其重儿子为其所有儿子中子树大小最大的那一个，重边为其连向重儿子的边。其余的则反过来，称为轻儿子和轻边。例如下图中的树：

• 每个点旁边用蓝笔写出了其重儿子；

  • 叉表示该点是叶子，没有儿子。
  • 像5 55这种有多个最大子树的，可以任选一个作为重儿子。

• 绿色的边就是重边。

像这种多个重边连起来的（如1 → 2 1 \to 21→2，2 → 5 2 \to 52→5，5 → 7 5 \to 75→7）（当然单个重边也是可以的）一条链就叫做重链，这条链最上面一个点（此处为1 11）就叫做该链的链头。对于一棵树上的任意一个点，我们有性质：

• 一个点最多向上跳O ( log ⁡ n ) O(\log n)O(logn)条重链就会跳到根。

理解一下这个性质。

• 首先，啥叫“跳”啊？

  • 跳就是，每一次跳到当前所在重链的链头的父亲。

• 如果一个点到其父亲的边不是重边呢？

  • 这里可以把这个点看作一个包含0 00个重边的重链，跳到其父亲即可。

• 为啥只会跳O ( log ⁡ n ) O(\log n)O(logn)次？

  • 感性理解一下，每次跳过一条重链，为了满足重链的性质（也就是重儿子的性质，其子树比其它子树都要大），可能的整个树的大小就要翻倍。所以这里只会跳O ( log ⁡ n ) O(\log n)O(logn)次。

这些信息都可以用一次 DFS 求出。这样就完成了我们的剖分过程，下面我们来看看这个有什么用。

如何用

来回到例题，看看树剖咋用。

首先我们基本就不会啥树上的数据结构，考虑把这棵树拍平到序列上，这样我们的操作就比较好进行了。

咋拍呢，我们也没学过啥别的啊，就直接用 DFS 序吧。

但是这样我们重链的优秀性质就没了——那怎么行！我们想到一个折中方案：DFS 的时候，如果该点不是叶子，那么先遍历重儿子。这样，一条重链上的点的 DFS 序就是连续的了。

看起来问题差不多解决了，因为子树修和子树和都可以用 DFS 序拍成区间加和区间求和。链也可以，因为有性质，我们直接一直向上跳就可以了。

但是我们怎么知道跳到哪里是 LCA 呢？如果 LCA 在一个重链中间怎么办？这里有一个解决办法：我们每次选链头深度大的那边跳上去，直到x xx和y yy在同一条重链上。因为 LCA 这个点至少有一个轻儿子（否则，x xx和y yy就已经在一条重链了，这里可以自行思考），所以总有一个点会正好跳到 LCA 上面。当跳到一条重链上面的时候，此时一个点是 LCA，另一个点一定是其后代，此时这两个点之间的链也一定在原来的x → y x \to yx→y路径上，而且 DFS 序也是连续的。

这就意味着，我们可以将一条链拆成序列上的O ( log ⁡ n ) O(\log n)O(logn)个连续区间，然后就可以直接线段树啦~

线段树就是区间加，区间求和就可以了。

分析一下复杂度：

• 空间上，没啥特别的，就是O ( n ) O(n)O(n)。

• 时间上，我们在跳重链的时候要跳O ( log ⁡ n ) O(\log n)O(logn)次，每次要花O ( log ⁡ n ) O(\log n)O(logn)的时间更新，所以总时间复杂度是O ( n log ⁡ 2 n ) O(n \log^2 n)O(nlog2n)。

代码比较好写。

:::info[Code]{open}

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e5+5;inta[N],dfnid;vector<int>e[N];intsiz[N],son[N],dep[N],fa[N],dfn[N],top[N],d[N];structsegtree{inttree[4*N],tag[4*N];voidpushup(intx){tree[x]=tree[x*2]+tree[x*2+1];}voidpushdown(intx,intl,intr){intmid=(l+r)>>1;tree[x*2]+=(mid-l+1)*tag[x];tree[x*2+1]+=(r-mid)*tag[x];tag[x*2]+=tag[x];tag[x*2+1]+=tag[x];tag[x]=0;}voidbuild(intx,intl,intr){if(l==r)returntree[x]=a[d[l]],tag[x]=0,void();intmid=(l+r)>>1;build(x*2,l,mid);build(x*2+1,mid+1,r);pushup(x);}voidupdate(intx,intl,intr,intL,intR,intd){if(R<l||L>r)return;if(L<=l&&r<=R)returntree[x]+=(r-l+1)*d,tag[x]+=d,void();pushdown(x,l,r);intmid=(l+r)>>1;update(x*2,l,mid,L,R,d);update(x*2+1,mid+1,r,L,R,d);pushup(x);}intquery(intx,intl,intr,intL,intR){if(R<l||L>r)return0;if(L<=l&&r<=R)returntree[x];pushdown(x,l,r);intmid=(l+r)>>1;returnquery(x*2,l,mid,L,R)+query(x*2+1,mid+1,r,L,R);}}tr;voiddfs1(intnow,intf){fa[now]=f;dep[now]=dep[f]+1;siz[now]=1;intmxsz=0,mxid=0;for(autox:e[now]){if(x==f)continue;dfs1(x,now);siz[now]+=siz[x];if(siz[x]>mxsz)mxsz=siz[x],mxid=x;}son[now]=mxid;}voiddfs2(intnow,intf,intrt){dfn[now]=++dfnid;top[now]=rt;if(son[now])dfs2(son[now],now,rt);for(autox:e[now]){if(x==f||x==son[now])continue;dfs2(x,now,x);}}signedmain(){intn,m,r,p;cin>>n>>m>>r>>p;for(inti=1;i<=n;i++)cin>>a[i];for(inti=1,u,v;i<n;i++)cin>>u>>v,e[u].push_back(v),e[v].push_back(u);dfs1(r,0);dfs2(r,0,r);for(inti=1;i<=n;i++)d[dfn[i]]=i;tr.build(1,1,n);while(m--){intopt,x,y,z;cin>>opt>>x;if(opt==1){cin>>y>>z;while(top[x]!=top[y]){if(dep[top[x]]>dep[top[y]])swap(x,y);tr.update(1,1,n,dfn[top[y]],dfn[y],z);y=fa[top[y]];}if(dep[x]>dep[y])swap(x,y);tr.update(1,1,n,dfn[x],dfn[y],z);}elseif(opt==2){cin>>y;intsum=0;while(top[x]!=top[y]){if(dep[top[x]]>dep[top[y]])swap(x,y);sum+=tr.query(1,1,n,dfn[top[y]],dfn[y]);y=fa[top[y]];}if(dep[x]>dep[y])swap(x,y);sum+=tr.query(1,1,n,dfn[x],dfn[y]);cout<<sum%p<<endl;}elseif(opt==3){cin>>z;tr.update(1,1,n,dfn[x],dfn[x]+siz[x]-1,z);}else{cout<<tr.query(1,1,n,dfn[x],dfn[x]+siz[x]-1)%p<<endl;}}return0;}

:::

练习题 1

• P3178 [HAOI2015] 树上操作
• P3833 [SHOI2012] 魔法树
• P2590 [ZJOI2008] 树的统计
• P2146 [NOI2015] 软件包管理器

这些题目只需稍微转换一下题意，或改一下线段树即可。

边权转点权

有些题需要我们维护的是边权，而不是点权，怎么办呢？

P4315 月下“毛景树”

给定一棵树，进行如下几种操作：

• Change k w：将第k kk条树枝上毛毛果的个数改变为w ww个。
• Cover u v w：将节点u uu与节点v vv之间的树枝上毛毛果的个数都改变为w ww个。
• Add u v w：将节点u uu与节点v vv之间的树枝上毛毛果的个数都增加w ww个。
• Max u v：询问节点u uu与节点v vv之间树枝上毛毛果个数最多有多少个。

n , q ≤ 10 5 n,q \le 10^5n,q≤105。

边权直接处理起来挺麻烦的，能不能想个办法转成点权呢？当然可以！我们让每个边里深度较大的那个点作为“代表”，把边权换成这个点的点权就好了。修改和查询的时候，需要注意不要把 LCA 也改了，因为 LCA 存的是它上面那条边，所以最后一次更新的时候从 LCA 的儿子开始即可。

练习题 2

• P1505 [国家集训队] 旅游
• P2680 [NOIP 2015 提高组] 运输计划

总结 & 后记

树链剖分是一种很常用（？的算法，可以和很多其他数据结构结合，灵活使用。

这篇主要是基础内容，后面如果需要可能（？会更进阶 qaq。

码字不易，能否给个赞 /wq ><

若对文章有任何问题和建议可以与作者私信交流。