树链剖分学习(复习?)笔记

树链剖分，即树剖。
顾名思义，树链剖分就是将一棵树通过某种方式剖分成若干条链，再利用 \(dfs\) 序，从而将树上的问题转化为序列上的问题。

树剖的方式有不止一种，比如重链剖分、长链剖分。最常用的(大概?)是重链剖分。此处介绍重链剖分。

首先，我们定义一个节点的重儿子为此节点的所有儿子中子树大小最大的一个（如果有多个就任取一个），其他的儿子为轻儿子。我们称这个节点与它的重儿子之间的边为重边，其余边为轻边，若干条重边构成的一条链为重链，并且我们把落单的点也视作重链，于是一棵树就被剖分为了若干条重链。

实现可以用两次 \(dfs\)，第一次 \(dfs\) 记录节点的深度 \(dep\)、子树大小 \(siz\) 和重儿子\(son\)。

\(Code:\)

il void dfs1(int x,int father,int depth){
	siz[x]=1,fa[x]=father,dep[x]=depth;
	for(re int i=head[x];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==father)continue;
		dfs1(v,x,depth+1);
		siz[x]+=siz[v];
		if(siz[v]>siz[son[x]])son[x]=v;
	}
}

重头戏：

第二次 \(dfs\)，我们对节点重新编号\((id)\)，并且我们在搜索的时候优先搜索重儿子。同时我们记录每个节点所在重链的起点 \(top\)。

\(Code:\)

il void dfs2(int x,int top_now){
	id[x]=++idx;
	a[idx]=b[x];
	top[x]=top_now;
	if(!son[x])return;
	dfs2(son[x],top_now);
	for(re int i=head[x];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==fa[x]||v==son[x])continue;
		dfs2(v,v);
	}
}

然后，因为是 \(dfs\) 序，所以同一棵子树上的节点编号 \(id\) 一定连续，又因为我们优先搜索重儿子，所以一条重链上的点编号 \(kid\) 也连续。于是我们就将树上问题转化为序列上的问题。

比如我们要实现单点修改、子树整体修改、路径修改、查询子树和、子树最大值、路径长度、路径上的最大值等等操作，就可以直接在树剖之后用线段树做。

具体来说，因为一棵子树内的编号 \(id\) 连续，所以它一定可以被表示为一段区间，那么我们直接在线段树上操作就好了。即：

update(id[x],id[x]+siz[x]-1)//更新以x为根的子树

对于路径上的操作，我们可以把这条路径剖分成若干条重链（数量在 \(log\) 级别以内，保证了复杂度）。然后将重链转化为区间，在线段树上进行操作。

il int GetSum_on_Path(int x,int y){
	int res=0;
	//一直跳重链直到x和y在同一条重链上
	//此处默认跳x，所以每次令x为深度更大的那个点
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		res+=GetSum(1,1,n,id[top[x]],id[x]);//丢给线段树
		x=fa[top[x]];
	}
	if(dep[x]<dep[y])swap(x,y);
	//因为在同一条重链上了，所以直接进行操作
	res+=GetSum(1,1,n,id[y],id[x]);
	return res;
}

\(update\) \(on\) \(230823:\)

然后就想起来两件事情：

\(1.\)关于时间复杂度

大概就是，每次从重链调到轻链的时候，点数规模至少下降一半？于是可以保证 \(log\) 的复杂度，并且大部分情况下跑不满，常数很小。

懂了，以后写 \(LCA\) 就用树剖了！反正倍增我已经忘记具体实现了

\(2.\)关于边信息转点信息

显然，要保证一一对应的话，直接把每条边的信息继承给它下方，或者说深度更大的一个点就好了。这个在第一次 \(dfs\) 的时候就可以实现，然后就是还有一个细节。呃，不好说，直接看代码吧。

il void update_Path(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		update(1,1,n,id[top[x]],id[x],1);
		x=fa[top[x]];
	}
	if(dep[x]<dep[y])swap(x,y);
	update(1,1,n,id[y],id[x],1);
	update(1,1,n,id[y],id[y],-1);
}

就是画一下图会发现有个地方是不该管的，把它去掉就ok了。