首页 > 其他分享 >树链剖分入门

树链剖分入门

时间：2022-11-09 15:02:48浏览次数：84  
标签：结点 入门 剖分 int siz top 树链 dfn 重链

树链剖分入门

本人初学，若有错误恳请大佬在评论区指出，谢谢！

一，它能干嘛

恶心你

解决树上路径/子树等问题。

情景引入

老师：给一棵点权树和一些操作，每次操作选两个点，把这两个点之间的路径上的点权加上一个数

同学：这不就是树上差分+LCA吗

老师：每次操作过后可能会问你两点之间的路径上的点权之和

同学：？？？？

老师：再加上子树操作

同学：群青.jpg

不扯了

比如Luogu的模板：P3384

已知一棵包含 \(N\) 个结点的树（连通且无环），每个节点上包含一个数值。
\(M\) 个操作：

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

\(N,M\le10^5\)

树链剖分可以在 \(O(n\log ^2 n)\) 的时间内解决这个问题。

二，怎么做

顾名思义，树链剖分就是要把树解剖成一条一条的链，然后把树上问题转换为区间问题，使用线段树等数据结构求解。树那么可爱你为什么要把它解剖了你食不食人啊

OI中一般采取轻重链剖分。

几个概念：

轻、重儿子：一个结点中的所有儿子中，子树大小最大的儿子为重儿子，其余为轻儿子。

轻、重边：连接父结点到重儿子的边叫做重边，连接父结点到轻儿子的边叫做轻边。

重链：由多条重边连接而成的路径。特别的，不在其他重链上的单个节点也算一条重链。

比如下面这棵树，重儿子用红色标出，重边用蓝色标出，方框内为重链：

image.png

写程序的准备

你要开这些东西：

int dep[M],dfn[M],rnk[M],fa[M],DFN,top[M],siz[M],hson[M];

dep：结点的深度。

dfn：结点的dfs序。（ 不是 欧拉序）

rnk：记录dfs序的第几位是几号结点。

fa：结点的父亲。

top：这个结点所在重链的链顶（深度最小的点）。

siz：子树大小

hson：重儿子的编号。

预处理

使用树剖要首先做两次遍历。

第一次：处理出每个结点的父亲、重儿子、子树大小、深度。

void dfs1(int x,int f){
	dep[x]=dep[f]+1;siz[x]=1;hson[x]=0;fa[x]=f;
	for(int i=h[x],v;v=e[i].v,i;i=e[i].nxt)if(v!=f){
		dfs1(v,x);siz[x]+=siz[v];
		if(siz[hson[x]]<siz[v])hson[x]=v;
	}
}

第二次：处理出每个结点的dfs序、rnk、链顶。

注意：这次dfs先走重儿子，待会说原因。

void dfs2(int x,int tp){
	dfn[x]=++DFN;rnk[DFN]=x;top[x]=tp;
	if(hson[x])dfs2(hson[x],tp);
	for(int i=h[x],v;v=e[i].v,i;i=e[i].nxt)if(v!=fa[x]&&v!=hson[x])dfs2(v,v);
}

这张图中结点上的小数字是dfn：

006JmRJEly1h7yqmxhnx0j30k40icdiw.jpg

接下来开一棵区间加区间求和的线段树并 build。

注意这棵线段树维护的是在dfn中的区间和，故 build 时赋值为 a[rnk[]]。

void build(int p=1,int s=1,int t=n){
	if(s==t){
		T[p]=a[rnk[s]];
		return;
	}
	build(LS,s,MID);build(RS,MID+1,t);
	pushup(p);
}

这两次dfs和线段树的 build 就是树剖的预处理。

那么如何询问呢？

子树加、子树求和

这个比较简单，根据dfs序的性质，一棵子树在dfs序中肯定是连续的一段。

因此直接找到子树根的 dfn，要查/改的区间就是 dfn[p],dfn[p]+siz[p]-1。

void modifysub(int p,int x){
	SGT::modify(dfn[p],dfn[p]+siz[p]-1,x);
}
int querysub(int p){
	return SGT::query(dfn[p],dfn[p]+siz[p]-1);
}

链加、链求和

前方高能

一条链在dfs序中好像没有什么规律可循...

...真的吗？

显然，所有的结点都有唯一一条重链与之对应。高中数学乱入

那么这意味着一条路径可以被拆成多条路径，每一条路径都只被一条重链包含。

考虑为什么我们要在标dfn的时候先走重儿子。

再仔细看看这个图，有没有什么头猪？

006JmRJEly1h7yqmxhnx0j30k40icdiw.jpg

没错，这样处理之后每条重链在dfs序上就是连续的一段了，从top向下递增。

那么我们就可以设计以下算法：

从两个查询的结点一直向上跳，每一次跳跃选取链顶深度较大的一个查询/修改对应重链链顶到这个点的区间和/执行区间加操作并跳到这条链链顶的父亲，直到跳到同一条重链上，再加上/修改剩下的一部分。

好绕啊

给个跳跃的图解（以求和为例）：

假设我们要查询结点8到结点6的和。

第一步：结点8的链顶比结点6的链顶更深，于是我们查询8的链顶（8）到8这一段dfs序内的和（[5,5]）并跳到4号结点。（用绿色圈出的点为已经加到答案的部分）

image.png

第二步：结点6的链顶比结点4的链顶更深，于是我们查询6的链顶（3）到6这一段dfs序内的和（[7,8]）并跳到1号结点。

image.png

第三步：结点4与结点1在同一条重链上，于是我们查询1到4这一段dfs序的和（[1,4]），结束。

image.png

因此，我们成功求出了两点之和。

顺便发现了新的求LCA算法

void modifych(int u,int v,int x){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])std::swap(u,v);
		SGT::modify(dfn[top[u]],dfn[u],x);u=fa[top[u]];
	}
	if(dep[u]>dep[v])std::swap(u,v);
	SGT::modify(dfn[u],dfn[v],x);

}
int querych(int u,int v){
	int ans=0;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])std::swap(u,v);
		ans=(ans+SGT::query(dfn[top[u]],dfn[u])%P)%P;u=fa[top[u]];
	}
	if(dep[u]>dep[v])std::swap(u,v);
	ans=(ans+SGT::query(dfn[u],dfn[v])%P)%P;
	return ans;
}

复杂度证明

显然，如果 \(u\) 是 \(v\) 的父亲且 \((u,v)\) 是一条轻边，那么 \(siz_u \ge 2siz_v\)（否则 \(u\) 的重儿子就应当是 \(v\)）

那么一条路径从LCA处拆开，两条路径上最多有 \(\log n\) 条重链。

乘上线段树的复杂度，因此链相关的操作复杂度为 \(\log^2 n\)，子树相关操作复杂度为 \(\log n\)。

模板完整代码

#include<cstdio>
#define int long long
const int M=1e5+5;
inline int read(){int x(0),op(0);char ch=getchar();while(ch<'0'||ch>'9')op|=(ch==45),ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return op?-x:x;}
int n,m,r,P;
int a[M];
struct edge{
	int v,nxt;
}e[M<<1];
int h[M],etot;
void adde(int u,int v){e[++etot]=(edge){v,h[u]};h[u]=etot;}
namespace HLD{
	int fa[M],siz[M],hson[M],dfn[M],top[M],rnk[M],dep[M];
	int DFN;
	void dfs1(int x,int f){
		dep[x]=dep[f]+1;siz[x]=1;hson[x]=0;fa[x]=f;
		for(int i=h[x],v;v=e[i].v,i;i=e[i].nxt)if(v!=f){
			dfs1(v,x);siz[x]+=siz[v];
			if(siz[hson[x]]<siz[v])hson[x]=v;
		}
	}
	void dfs2(int x,int tp){
		dfn[x]=++DFN;rnk[DFN]=x;top[x]=tp;
		if(hson[x])dfs2(hson[x],tp);
		for(int i=h[x],v;v=e[i].v,i;i=e[i].nxt)if(v!=fa[x]&&v!=hson[x])dfs2(v,v);
	}
	namespace SGT{
		#define LS (p<<1)
		#define RS ((p<<1)|1)
		#define MID ((s+t)>>1)
		int T[M<<2],tag[M<<2];
		void pushup(int p){T[p]=(T[LS]+T[RS])%P;}
		void pushdown(int p,int s,int t){
			if(tag[p]){
				T[LS]=(T[LS]+(tag[p]*(MID-s+1))%P)%P;T[RS]=(T[RS]+(tag[p]*(t-MID))%P)%P;
				tag[LS]=(tag[LS]+tag[p])%P;tag[RS]=(tag[RS]+tag[p])%P;
			}
			tag[p]=0;
		}
		void build(int p=1,int s=1,int t=n){
			if(s==t){
				T[p]=a[rnk[s]];
				return;
			}
			build(LS,s,MID);build(RS,MID+1,t);
			pushup(p);
		}
		int query(int l,int r,int p=1,int s=1,int t=n){
			if(t<l||r<s)return 0;
			if(l<=s&&t<=r)return T[p];
			pushdown(p,s,t);
			return (query(l,r,LS,s,MID)+query(l,r,RS,MID+1,t))%P;
		}
		void modify(int l,int r,int x,int p=1,int s=1,int t=n){
			if(t<l||r<s)return;
			if(l<=s&&t<=r){
				T[p]=(T[p]+(t-s+1)*x%P)%P;
				tag[p]=(tag[p]+x)%P;
				return;
			}
			pushdown(p,s,t);
			modify(l,r,x,LS,s,MID);modify(l,r,x,RS,MID+1,t);
			pushup(p);
		}
	}
	void init(){dfs1(r,0);dfs2(r,r);SGT::build();}
	void modifych(int u,int v,int x){
		while(top[u]!=top[v]){
			if(dep[top[u]]<dep[top[v]])std::swap(u,v);
			SGT::modify(dfn[top[u]],dfn[u],x);u=fa[top[u]];
		}
		if(dep[u]>dep[v])std::swap(u,v);
		SGT::modify(dfn[u],dfn[v],x);
	}
	void modifysub(int p,int x){
		SGT::modify(dfn[p],dfn[p]+siz[p]-1,x);
	}
	int querych(int u,int v){
		int ans=0;
		while(top[u]!=top[v]){
			if(dep[top[u]]<dep[top[v]])std::swap(u,v);
			ans=(ans+SGT::query(dfn[top[u]],dfn[u])%P)%P;u=fa[top[u]];
		}
		if(dep[u]>dep[v])std::swap(u,v);
		ans=(ans+SGT::query(dfn[u],dfn[v])%P)%P;
		return ans;
	}
	int querysub(int p){
		return SGT::query(dfn[p],dfn[p]+siz[p]-1);
	}
}
signed main(){
	n=read(),m=read(),r=read(),P=read();
	for(int i=1;i<=n;++i)a[i]=read();
	for(int i=1;i<n;++i){
		int u=read(),v=read();
		adde(u,v);adde(v,u);
	}
	HLD::init();
	while(m--){
		int op=read(),u=read();
		if(op<4){
			int v=read();
			if(op==1){
				int x=read();
				HLD::modifych(u,v,x);
			}
			else if(op==2){
				printf("%lld\n",HLD::querych(u,v));
			}
			else HLD::modifysub(u,v);
		}
		else printf("%lld\n",HLD::querysub(u));
	}
	return 0;
}

例题

LuoguP2590

建议改为：树链剖分模板2。

代码：咕了

LuoguP3178

建议改为：树链剖分模板3。

代码：（std::vector ver.）

#include<cstdio>
#include<vector>
#define int long long
const int M=1e5+5;
inline int read(){int x(0),op(0);char ch=getchar();while(ch<'0'||ch>'9')op|=(ch==45),ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return op?-x:x;}
int n,m,r,P;
int a[M];
namespace HLD{
	std::vector<int> T[M];
	int fa[M],siz[M],hson[M],dfn[M],top[M],rnk[M],dep[M];
	int DFN;
	namespace SGT{
		#define LS (p<<1)
		#define RS ((p<<1)|1)
		#define MID ((s+t)>>1)
		int SGT[M<<2],tag[M<<2];
		void pushup(int p){SGT[p]=SGT[LS]+SGT[RS];}
		void pushdown(int p,int s,int t){
			if(tag[p]){
				SGT[LS]+=tag[p]*(MID-s+1);SGT[RS]+=tag[p]*(t-MID);
				tag[LS]+=tag[p];tag[RS]+=tag[p];
			}
			tag[p]=0;
		}
		void build(int p=1,int s=1,int t=n){
			if(s==t){
				SGT[p]=a[rnk[s]];
				return;
			}
			build(LS,s,MID);build(RS,MID+1,t);
			pushup(p);
		}
		int query(int l,int r,int p=1,int s=1,int t=n){
			if(t<l||r<s)return 0;
			if(l<=s&&t<=r)return SGT[p];
			pushdown(p,s,t);
			return query(l,r,LS,s,MID)+query(l,r,RS,MID+1,t);
		}
		void modify(int l,int r,int x,int p=1,int s=1,int t=n){
			if(t<l||r<s)return;
			if(l<=s&&t<=r){
				SGT[p]+=(t-s+1)*x;tag[p]+=x;
				return;
			}
			pushdown(p,s,t);
			modify(l,r,x,LS,s,MID);modify(l,r,x,RS,MID+1,t);
			pushup(p);
		}
	}
	void dfs1(int x,int f){
		fa[x]=f;siz[x]=1;hson[x]=0;dep[x]=dep[f]+1;
		for(auto v:T[x])if(v!=f){
			dfs1(v,x);
			siz[x]+=siz[v];
			if(siz[v]>siz[hson[x]])hson[x]=v;
		}
	}
	void dfs2(int x,int f){
		dfn[x]=++DFN;rnk[dfn[x]]=x;top[x]=f;
		if(!hson[x])return;
		dfs2(hson[x],f);
		for(auto v:T[x])if(v!=fa[x]&&v!=hson[x])dfs2(v,v);		
	}
	void init(){
		dfs1(r,0);
		dfs2(r,r);
		SGT::build();
	}
	void modifypt(int p,int x){
		SGT::modify(dfn[p],dfn[p],x);
	}
	void modifysub(int p,int x){
		SGT::modify(dfn[p],dfn[p]+siz[p]-1,x);
	}
	int querych(int u,int v){
		int ans=0;
		while(top[u]!=top[v]){
			if(dep[top[u]]<dep[top[v]])std::swap(u,v);
			ans+=SGT::query(dfn[top[u]],dfn[u]);u=fa[top[u]];
		}
		if(dep[u]>dep[v])std::swap(u,v);
		ans+=SGT::query(dfn[u],dfn[v]);
		return ans;
	}
}
signed main(){
	n=read(),m=read(),r=1;
	for(int i=1;i<=n;++i)a[i]=read();
	for(int i=1;i<n;++i){
		int u=read(),v=read();
		HLD::T[u].push_back(v);HLD::T[v].push_back(u);
	}
	HLD::init();
	while(m--){
		int op=read(),u=read();
		if(op<3){
			int k=read();
			if(op==1)HLD::modifypt(u,k);
			else HLD::modifysub(u,k);
		}
		else printf("%lld\n",HLD::querych(1,u));
	}
	return 0;
}

LuoguP2146

建议改为：树链剖分模板4

好吧还是要想想的。

这道题可以转换为：

一棵树，初始所有点点权为0。

两种操作：

  1. 选一个结点，把它到根的路径上所有点点权改为1，并询问改之前和改之后路径上点权和的差。

  2. 选一个结点，把它的子树中所有点点权改为0，并询问改之前和改之后子树中点权和的差。

于是成裸题了。

代码：咕了

LuoguP2486

难点在线段树上。

线段树记左右端点的颜色以及求的答案，query合并答案的时候如果左区间的最右颜色和右区间最左颜色相同答案减1。

加个懒标记即可。

代码：咕了

咕了的代码有（zai）空（ye）再（bu）写（xie）吧（le）

三，换根树剖

LOJ139

和Luogu模板不同的是，这道题有一个换根操作。

显然你不可能换一次根就重新预处理一遍除非你能 \(n^2\) 过十万

但是换根是不影响链操作的，所以讨论子树操作怎么搞。

显然，有3种情况：

  1. 现在的根不在操作结点的子树内：说明这个结点的子树没变，这种情况下直接像原来那样就行了。

  2. 现在的根就是要操作的结点：直接全局操作就好了。

  3. 现在的根在操作结点的子树内：相当于要操作含根子树以外的所有结点，因此我们要找出哪个子树包含当前的根。

我们从现在的根沿着重链一步一步的向上跳，直到跳到当前操作结点的重链上或者该重链链顶的父亲就是操作结点。

第一种情况下，操作结点的重儿子即为所求；第二种情况下，该重链的链顶即为所求。

int getson(int x,int y){
	for(;top[x]!=top[y];x=fa[top[x]])if(fa[top[x]]==y)return top[x];
	return hson[y];
}

AC记录

啊终于写完了累死我了

有空更新。

标签：结点,入门,剖分,int,siz,top,树链,dfn,重链
From： https://www.cnblogs.com/pokefunc/p/16873125.html

相关文章

  • HummerRisk 快速入门教程
    1、一键部署1.部署服务器要求操作系统要求：任何支持Docker的Linuxx64CPU内存要求：最低要求4C8G，推荐8C16G部署目录空间（默认/opt目录）要求：50G网络要求：可访问互联网（如遇内......
  • k8s实战入门——Deployment
    Deployment在kubernetes中，Pod是最小的控制单元，但是kubernetes很少直接控制Pod，一般都是通过Pod控制器来完成的。Pod控制器用于pod的管理，确保pod资源符合预期的状态，当pod的......
  • 超详细的QSS样式表入门Demo
    超详细的QSS样式表入门Demo_mahuifa的博客-CSDN博客_qss样式超详细的QSS样式表入门Demomahuifa已于 2022-08-0222:52:28 修改2717收藏165分......
  • 带你少走弯路：强烈推荐的Keras快速入门资料和翻译（可下载）
    上次写了TensorFlow和PyTorch的快速入门资料，受到很多好评，读者强烈建议我再出一个keras的快速入门路线，经过翻译和搜索网上资源，我推荐4份入门资料，希望对大家有所帮助。备注：另......
  • OpenCV官方免费视频教程->快速入门OpenCV与AI使用 (视频 + 源码)
    课程介绍  OpenCV官方发布的免费OpenCV速成视频教程。本课程将帮助您迈出使用OpenCV学习计算机视觉和AI的第一步。您将学习并接触到各种令人兴奋的主题，例如图像和......
  • 使用OkHttp发送POST请求的快速入门指南
    英文原文：https://www.baeldung.com/okhttp-post1介绍本文将介绍OkHttp客户端的基本用法。在本篇简短的技术文章中，我们将特别介绍OkHttp3.x版本中发送Post请求的不......
  • 尚硅谷java入门b站零基础 异常处理 +多线程+部分项目三 2022.3.26
    380如何自定义异常/**如何自定义异常类？*1.继承于现有的异常结构：RuntimeException、Exception*2.提供全局常量：serialVersionUID*3.提供重载的构造器**/publicc......
  • 尚硅谷Java入门哔哩哔哩274p-289p(2022.3.12)
    274super调用属性和方法super关键字的使用1.super理解为：父类的2.super可以用来调用：属性，方法，构造器3.super的使用：调用属性和方法 3.1我们可以在子类的方法或构造器中，通过......
  • 尚硅谷java零基础入门从221p开始的笔记
    221***面向对象上四种权限修饰的理解封装性的体现需要权限修饰符来配合1.java规定的四种权限（从小到大排列）private，缺省，protected，publicpublic类可以在任意地方被访问pr......
  • 尚硅谷java入门bilibili（290p-303p）2022.3.13
    290p多态性练习：几何图形*定义三个类，父类GeometricObject代表几何形状，子类Circle代表圆形，MyRectangle代表矩形publicclassGeometricObject{//几何图形protectedSt......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99