首页 > 其他分享 >树链剖分学习笔记

树链剖分学习笔记

时间：2024-02-26 22:01:24浏览次数：25  
标签：剖分 top tr 笔记 树链 dfn 节点 重链 ll

树链剖分学习笔记

树链剖分的思想及能解决的问题

树链剖分用于将树分割成若干条链的形式，以维护树上路径的信息。

具体来说，将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息。

树链剖分（树剖/链剖）有多种形式，如 重链剖分，长链剖分 和用于 Link/cut Tree 的剖分（有时被称作「实链剖分」），大多数情况下（没有特别说明时），「树链剖分」都指「重链剖分」。

重链剖分可以将树上的任意一条路径划分成不超过 $O(\log n)$ 条连续的链，每条链上的点深度互不相同（即是自底向上的一条链，链上所有点的 LCA 为链的一个端点）。

重链剖分还能保证划分出的每条链上的节点 DFS 序连续，因此可以方便地用一些维护序列的数据结构（如线段树）来维护树上路径的信息。

如：

  1. 修改 树上两点之间的路径上 所有点的值。
  2. 查询 树上两点之间的路径上 节点权值的 和/极值/其它（在序列上可以用数据结构维护，便于合并的信息）。

除了配合数据结构来维护树上路径信息，树剖还可以用来 $O(\log n)$（且常数较小）地求 LCA。在某些题目中，还可以利用其性质来灵活地运用树剖。

重链剖分

我们给出一些定义：

定义 重子节点 表示其子节点中子树最大的子结点。如果有多个子树最大的子结点，取其一。如果没有子节点，就无重子节点。

定义 轻子节点 表示剩余的所有子结点。

从这个结点到重子节点的边为 重边。

到其他轻子节点的边为 轻边。

若干条首尾衔接的重边构成 重链。

把落单的结点也当作重链，那么整棵树就被剖分成若干条重链。

如图：

实现

树剖的实现分两个 DFS 的过程。伪代码如下：

第一个 DFS 记录每个结点的父节点（father）、深度（deep）、子树大小（size）、重子节点（hson）。
$$
\begin{array}{l} \text{TREE-BUILD }(u,dep) \ \begin{array}{ll} 1 & u.hson\gets 0 \ 2 & u.hson.size\gets 0 \ 3 & u.deep\gets dep \ 4 & u.size\gets 1 \ 5 & \textbf{for }\text{each }u\text{'s son }v \ 6 & \qquad u.size\gets u.size + \text{TREE-BUILD }(v,dep+1) \ 7 & \qquad v.father\gets u \ 8 & \qquad \textbf{if }v.size> u.hson.size \ 9 & \qquad \qquad u.hson\gets v \ 10 & \textbf{return } u.size \end{array} \end{array}
$$

第二个 DFS 记录所在链的链顶（top，应初始化为结点本身）、重边优先遍历时的 DFS 序（dfn）、DFS 序对应的节点编号（rank）。
$$
\begin{array}{l} \text{TREE-DECOMPOSITION }(u,top) \ \begin{array}{ll} 1 & u.top\gets top \ 2 & tot\gets tot+1\ 3 & u.dfn\gets tot \ 4 & rank(tot)\gets u \ 5 & \textbf{if }u.hson\text{ is not }0 \ 6 & \qquad \text{TREE-DECOMPOSITION }(u.hson,top) \ 7 & \qquad \textbf{for }\text{each }u\text{'s son }v \ 8 & \qquad \qquad \textbf{if }v\text{ is not }u.hson \ 9 & \qquad \qquad \qquad \text{TREE-DECOMPOSITION }(v,v) \end{array} \end{array}
$$

以上为代码实现。

我们先给出一些定义：

  • $fa(x)$ 表示节点 $x$ 在树上的父亲。
  • $dep(x)$ 表示节点 $x$ 在树上的深度。
  • $siz(x)$ 表示节点 $x$ 的子树的节点个数（包括自己）。
  • $son(x)$ 表示节点 $x$ 的 重儿子。
  • $top(x)$ 表示节点 $x$ 所在 重链 的顶部节点（深度最小)。
  • $dfn(x)$ 表示节点 $x$ 的 DFS 序，也是其在线段树中的编号。
  • $rnk(x)$ 表示 DFS 序所对应的节点编号，有 $rnk(dfn(x))=x$。

我们进行两遍 DFS 预处理出这些值，其中第一次 DFS 求出 $fa(x)$，$dep(x)$，$siz(x)$，$son(x)$，第二次 DFS 求出 $top(x)$，$dfn(x)$，$rnk(x)$。

/*定义部分*/
ll n, a, b, w[Maxn];
vector<ll> v[Maxn];
ll fa[Maxn], dep[Maxn], siz[Maxn], son[Maxn];
ll top[Maxn], dfncnt=0, dfn[Maxn], rnk[Maxn];
/*定义部分*/

void dfs1(ll x){
	son[x]=-1, siz[x]=1; // son为-1表示为叶子节点，siz包括本身
	for(ll i=0;i<(ll)v[x].size();i++){
		ll tmp=v[x][i];
		if(!dep[tmp]){
			dep[tmp]=dep[x]+1, fa[tmp]=x;
			dfs1(tmp);
			siz[x]+=siz[tmp];
			son[x]=((son[x]==-1 || siz[tmp]>siz[son[x]]) ? tmp : son[x]); // 求重子节点
		}
	}
} void dfs2(ll x, ll Top){
	top[x]=Top, dfn[x]=++dfncnt; // dfn
	rnk[dfncnt]=x;
	if(son[x]==-1){ return ; } // 叶子节点
	dfs2(son[x], Top); // 更新重链上的点的信息
	for(ll i=0;i<(int)v[x].size();i++){
		ll tmp=v[x][i];
		if(tmp!=son[x] && tmp!=fa[x]){ // 既不为重子节点，也不为父亲节点
			dfs2(tmp, tmp); // 新的重链
		}
	}
}

重链剖分的性质

树上每个节点都属于且仅属于一条重链。

重链开头的结点不一定是重子节点（因为重边是对于每一个结点都有定义的）。

所有的重链将整棵树 完全剖分。

在剖分时 重边优先遍历，最后树的 DFS 序上，重链内的 DFS 序是连续的。按 DFN 排序后的序列即为剖分后的链。

一颗子树内的 DFS 序是连续的。

可以发现，当我们向下经过一条 轻边 时，所在子树的大小至少会除以二。

因此，对于树上的任意一条路径，把它拆分成从 LCA 分别向两边往下走，分别最多走 $O(\log n)$ 次，因此，树上的每条路径都可以被拆分成不超过 $O(\log n)$ 条重链。

常见应用

路径上维护

用树链剖分求树上两点路径权值和，伪代码如下：
$$
\begin{array}{l} \text{TREE-PATH-SUM }(u,v) \ \begin{array}{ll} 1 & tot\gets 0 \ 2 & \textbf{while }u.top\text{ is not }v.top \ 3 & \qquad \textbf{if }u.top.deep< v.top.deep \ 4 & \qquad \qquad \text{SWAP}(u, v) \ 5 & \qquad tot\gets tot + \text{sum of values between }u\text{ and }u.top \ 6 & \qquad u\gets u.top.father \ 7 & tot\gets tot + \text{sum of values between }u\text{ and }v \ 8 & \textbf{return } tot \end{array} \end{array}
$$

链上的 DFS 序是连续的，可以使用线段树、树状数组维护。

每次选择深度较大的链往上跳，直到两点在同一条链上。

同样的跳链结构适用于维护、统计路径上的其他信息。

子树维护

有时会要求，维护子树上的信息，譬如将以 $x$ 为根的子树的所有结点的权值增加 $v$。

在 DFS 搜索的时候，子树中的结点的 DFS 序是连续的。

每一个结点记录 bottom 表示所在子树连续区间末端的结点。

这样就把子树信息转化为连续的一段区间信息。

求最近公共祖先

不断向上跳重链，当跳到同一条重链上时，深度较小的结点即为 LCA。

向上跳重链时需要先跳所在重链顶端深度较大的那个。

参考代码：

ll LCA(ll x, ll y){
	while(top[x]!=top[y]){
		if(dep[top[x]]>dep[top[y]]){
			x=fa[x];
		} else{
			y=fa[y];
		}
	}
	return (dep[x]>dep[y] ? y : x);
}

例题

「ZJOI2008」树的统计

题目大意

对一棵有 $n$ 个节点，节点带权值的静态树，进行三种操作共 $q$ 次：

  1. 修改单个节点的权值；
  2. 查询 $u$ 到 $v$ 的路径上的最大权值；
  3. 查询 $u$ 到 $v$ 的路径上的权值之和。

保证 $ 1\le n\le 30000$，$0\le q\le 200000$。

解法

根据题面以及以上的性质，你的线段树需要维护三种操作：

  1. 单点修改；
  2. 区间查询最大值；
  3. 区间查询和。

单点修改很容易实现。

由于子树的 DFS 序连续（无论是否树剖都是如此），修改一个节点的子树只用修改这一段连续的 DFS 序区间。

问题是如何修改/查询两个节点之间的路径。

考虑我们是如何用 倍增法求解 LCA 的。首先我们 将两个节点提到同一高度，然后将两个节点一起向上跳。对于树链剖分也可以使用这样的思想。

在向上跳的过程中，如果当前节点在重链上，向上跳到重链顶端，如果当前节点不在重链上，向上跳一个节点。如此直到两节点相同。沿途更新/查询区间信息。

对于每个询问，最多经过 $O(\log n)$ 条重链，每条重链上线段树的复杂度为 $O(\log n)$，因此总时间复杂度为 $O(n\log n+q\log^2 n)$。实际上重链个数很难达到 $O(\log n)$(可以用完全二叉树卡满)，所以树剖在一般情况下常数较小。

给出一种代码实现：

ll Q_max(ll x, ll y){
	ll maxl=-INF;
	while(top[x]!=top[y]){
		if(dep[top[x]]>=dep[top[y]]){ // 看哪一个更靠下 == 看哪一个更深 == 看哪一个 dep 值大
			maxl=max(maxl, Q.Max(1, dfn[top[x]], dfn[x])), x=fa[top[x]]; // 一定是f[top[x]]
		} else{
			maxl=max(maxl, Q.Max(1, dfn[top[y]], dfn[y])), y=fa[top[y]]; // 一定是f[top[y]]
		}
	}
	
	if(dfn[x]<dfn[y]){
		maxl=max(maxl, Q.Max(1, dfn[x], dfn[y]));
	} else{
		maxl=max(maxl, Q.Max(1, dfn[y], dfn[x]));
	}
	return maxl;
}

ll Q_sum(ll x, ll y){
	ll sum=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]>=dep[top[y]]){
			sum+=Q.Sum(1, dfn[top[x]], dfn[x]), x=fa[top[x]]; // 一定是f[top[x]]
		} else{
			sum+=Q.Sum(1, dfn[top[y]], dfn[y]), y=fa[top[y]]; // 一定是f[top[y]]
		}
	}
	
	if(dfn[x]<dfn[y]){
		sum+=Q.Sum(1, dfn[x], dfn[y]);
	} else{
		sum+=Q.Sum(1, dfn[y], dfn[x]);
	}
	return sum;
} // 整体同 Q_max 函数

#include<bits/stdc++.h>
#define ll long long
#define Maxn 30005
#define INF 2147483647

using namespace std;

ll n, a, b, w[Maxn];
ll q, x, y;
string opt;
vector<ll> v[Maxn];
ll fa[Maxn], dep[Maxn], siz[Maxn], son[Maxn];
ll top[Maxn], dfncnt=0, dfn[Maxn], rnk[Maxn];

void dfs1(ll x){
	son[x]=-1, siz[x]=1; // son为-1表示为叶子节点，siz包括本身
	for(ll i=0;i<(ll)v[x].size();i++){
		ll tmp=v[x][i];
		if(!dep[tmp]){
			dep[tmp]=dep[x]+1, fa[tmp]=x;
			dfs1(tmp);
			siz[x]+=siz[tmp];
			son[x]=((son[x]==-1 || siz[tmp]>siz[son[x]]) ? tmp : son[x]); // 求重子节点
		}
	}
} void dfs2(ll x, ll Top){
	top[x]=Top, dfn[x]=++dfncnt; // dfn
	rnk[dfncnt]=x;
	if(son[x]==-1){ return ; } // 叶子节点
	dfs2(son[x], Top); // 更新重链上的点的信息
	for(ll i=0;i<(int)v[x].size();i++){
		ll tmp=v[x][i];
		if(tmp!=son[x] && tmp!=fa[x]){ // 既不为重子节点，也不为父亲节点
			dfs2(tmp, tmp); // 新的重链
		}
	}
}
//线段树的节点编号是dfn

struct Seg_tree{
#define lid (id<<1)
#define rid (id<<1|1)
	struct SG_TR{
		ll l, r, maxl, sum;
	} tr[Maxn<<2];
	
	void build(ll id, ll l, ll r){ // 建树
		tr[id].l=l, tr[id].r=r;
		if(l==r){
			tr[id].maxl=tr[id].sum=w[rnk[l]];
			return ;
		}
		
		ll mid=(l+r)>>1;
		build(lid, l, mid), build(rid, mid+1, r);
		tr[id].sum=tr[lid].sum+tr[rid].sum;
		tr[id].maxl=max(tr[lid].maxl, tr[rid].maxl);
	}
	
	void update(ll id, ll x, ll val){ // 更新
		if(tr[id].l==tr[id].r){
			if(tr[id].l==x){
				tr[id].maxl=tr[id].sum=val;
			}
			return ;
		}
		
		ll mid=(tr[id].l+tr[id].r)>>1;
		if(x<=mid){ update(lid, x, val); }
		else if(x>mid){ update(rid, x, val); }
		tr[id].sum=tr[lid].sum+tr[rid].sum;
		tr[id].maxl=max(tr[lid].maxl, tr[rid].maxl);
	}
	
	ll Max(ll id, ll l, ll r){ // 求区间最大
		if(tr[id].l==l && tr[id].r==r){
			return tr[id].maxl;
		}
		
		ll mid=(tr[id].l+tr[id].r)>>1;
		if(r<=mid){ return Max(lid, l, r); }
		else if(l>mid){ return Max(rid, l, r); }
		else{ return max(Max(lid, l, mid), Max(rid, mid+1, r)); }
	}
	
	ll Sum(ll id, ll l, ll r){ // 求区间和
		if(tr[id].l==l && tr[id].r==r){
			return tr[id].sum;
		}
		
		ll mid=(tr[id].l+tr[id].r)>>1;
		if(r<=mid){ return Sum(lid, l, r); }
		else if(l>mid){ return Sum(rid, l, r); }
		else{ return Sum(id, l, mid)+Sum(rid, mid+1, r); }
	}
} Q; // 结构体封装线段树

ll Q_max(ll x, ll y){
	ll maxl=-INF;
	while(top[x]!=top[y]){
		if(dep[top[x]]>=dep[top[y]]){ // 看哪一个更靠下 == 看哪一个更深 == 看哪一个 dep 值大
			maxl=max(maxl, Q.Max(1, dfn[top[x]], dfn[x])), x=fa[top[x]]; // 一定是f[top[x]]
		} else{
			maxl=max(maxl, Q.Max(1, dfn[top[y]], dfn[y])), y=fa[top[y]]; // 一定是f[top[y]]
		}
	}
	
	if(dfn[x]<dfn[y]){
		maxl=max(maxl, Q.Max(1, dfn[x], dfn[y]));
	} else{
		maxl=max(maxl, Q.Max(1, dfn[y], dfn[x]));
	}
	return maxl;
}

ll Q_sum(ll x, ll y){
	ll sum=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]>=dep[top[y]]){
			sum+=Q.Sum(1, dfn[top[x]], dfn[x]), x=fa[top[x]]; // 一定是f[top[x]]
		} else{
			sum+=Q.Sum(1, dfn[top[y]], dfn[y]), y=fa[top[y]]; // 一定是f[top[y]]
		}
	}
	
	if(dfn[x]<dfn[y]){
		sum+=Q.Sum(1, dfn[x], dfn[y]);
	} else{
		sum+=Q.Sum(1, dfn[y], dfn[x]);
	}
	return sum;
} // 整体同 Q_max 函数

int main()
{
	cin>>n;
	for(ll i=1;i<n;i++){
		cin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
	} for(ll i=1;i<=n;i++){
		cin>>w[i];
	}
	dep[1]=1, dfs1(1), dfs2(1, 1), Q.build(1, 1, n);
	
	cin>>q;
	for(ll i=1;i<=q;i++){
		cin>>opt>>x>>y;
		if(opt[1]=='H'){ // CHANGE
			Q.update(1, dfn[x], y);
		} else if(opt[1]=='M'){ // MAX
			cout<<Q_max(x, y)<<endl;
		} else if(opt[1]=='S'){ // SUM
			cout<<Q_sum(x, y)<<endl;
		}
	}
	return 0;
}

标签：剖分,top,tr,笔记,树链,dfn,节点,重链,ll
From： https://www.cnblogs.com/BLM-dolphin/p/18035671

相关文章

  • 组合数学学习笔记
    组合数学及相关计数法一、计数原理1.加法原理举个例子：从甲地到乙地共有海陆空三种选择，坐船有$3$班，坐车有$5$班，坐飞机有$2$班，问从甲地到乙地共有几种选择？解：这是一个幼儿园的题$3+5+2=10$加法原理（分类计数原理）：完成一件事共有$n$类方法，第一类有$a_1$种方案，第二类有$......
  • 第十章 通过汇编语言了解程序的实际构成 笔记
    编语言是介于机器语言和高级编程语言之间的一种语言。它使用助记符来表示CPU指令，这些助记符相较于机器语言的二进制编码更为人类可读。虽然汇编语言比高级语言更难以编写和理解，但它能够提供对程序行为的直接控制，以及与计算机硬件架构密切相关的通过学习汇编语言，我们可以了解程序......
  • 【机器学习科学库】全md文档笔记：Matplotlib详细使用方法（已分享，附代码）
    本系列文章md笔记（已分享）主要讨论人工智能相关知识。主要内容包括，了解机器学习定义以及应用场景，掌握机器学习基础环境的安装和使用，掌握利用常用的科学计算库对数据进行展示、分析，学会使用jupyternotebook平台完成代码编写运行，应用Matplotlib的基本功能实现图形显示，应用Matplotlib......
  • CTF之RCE笔记
    https://www.ctfhub.com/#/skilltree命令注入命令注入，查看当前文件夹结构?ip=127.0.0.1;ls查看php文件内容?ip=127.0.0.1;cat11001571914029.php提交flag，成功破解过滤cat命令注入，查看当前文件夹结构?ip=127.0.0.1;ls使用cat尝试读取php文件?ip=127.0.0.1;catfla......
  • 【学习笔记】树型DP学习笔记
    学习笔记索引省流：被吊打了自己开的一个坑，死也要填完它。希望我随手写下的笔记对您的学习有所帮助（也不太可能）。更改日志2024/01/08：开坑，写了树的直径和换根DP，写不动了（（（2024/01/08晚上：更新了最小点覆盖和最大独立集，看来精神还可以，顶着明天做手术的风险2024/01/09：修改错误+增补......
  • 【学习笔记】倍增ST表、LCA学习笔记
    学习笔记索引众所周知，scy5赛时在P10059Choose写了个滑动窗口骗\(40\)分，但是狂WA不止，丢掉了\(rk155\)，于是就有了下面这两张口吐芬芳的图：听说这题可以用ST表做，但他不会，于是他就来学倍增乐。省流：被吊打了更改日志2024/01/16：开坑。倍增原理设做一件事有\(n\)个步骤。......
  • 【学习笔记】分块学习笔记
    学习笔记索引分块经常听别人提起，我也学一下。正片分块就是将一个数列分成很多块，然后每块单独操作，最后的结果放到原数列里。分块的题目类型经常是区间中修改和查询。这里，一个长度为\(n\)的数列最多分成\(\sqrtn\)个块。先来看例题吧。例题P2357守墓人题目背景在一......
  • 【Django开发】0到1开发美多shop项目：用户登录模块开发。全md文档笔记（附代码 文档）
    本系列文章md笔记（已分享）主要讨论django商城项目相关知识。项目利用Django框架开发一套前后端不分离的商城项目（4.0版本）含代码和文档。功能包括前后端不分离，方便SEO。采用Django+Jinja2模板引擎+Vue.js实现前后端逻辑，Nginx服务器（反向代理）Nginx服务器（静态首页、商品详情页、uwsg......
  • Vue学习笔记16--监视属性watch + 深度监视 + 监视简写
    监视属性watch示例一：<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metaname="viewport"content="width=device-width,initial-scale=1.0"><title>计算属性</title&......
  • 标记永久化【学习笔记】
    众所周知，线段树最重要的操作之一便是标记下传。但在一些情况下，我们不能进行标记的下传（可能是正确性的问题、或者是复杂度的问题）正确性问题：比如带修的可持久化线段树中，如果标记下传，会影响之前的版本。复杂度问题：比如树套树中，push_up操作的复杂度会直接炸掉。因此，就产生了标记永......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99