[学习笔记]树链剖分(简易版) 及其LCA

树链剖分

先讲解一下一些基础定义(都是在树上)

• 重儿子: 一个节点中所有儿子中子树大小最大的一个儿子(每个节点最多有一个重儿子)
• 轻儿子: 一个节点除重儿子外所有的节点
• 重链: 若干个重儿子组成的链
• 链顶: 一条链中深度最小的节点

以下图为例子 (红色连续线段为重链)

对于节点 $1$ 来说, 子树大小最大的儿子是 $2$ , $2$ 最大的是 $5$ , $5$的所有儿子子树大小一样大, 随机选一个即可
对于节点 $3$ 来说, 虽然本身是一个轻儿子, 但是它有重儿子 $4$ , 所以也能构成一条重链
由此观之, 所有的点都在某条重链上(重链可能是一个点)

现在, 我们可以通过 $dfs$ 求出以任意节点为根的子树大小, 并且通过全部比较找出每个节点的重儿子.
之后再次 $dfs$ , 把重儿子连成一条又一条链, 记录每个节点所在链的链顶, 等会 $LCA$ 要用

//知道原理就自己写吧, 我的码风一言难尽, 学长写了50行, 我写了270行, 删完之后还剩150行
void dfs(int now,int father){
	for(int x=0;x<g[now].size();x++){
		node to=g[now][x];
		if(to.v==father){
			continue;
		}
		fa[to.v]=now;
		dfs(to.v,now);
		siz[now]+=siz[to.v];
	}
	return;
}

void dfss(int now,int father){
	int num=0,maxn=-1;
	for(int x=0;x<g[now].size();x++){
		node to=g[now][x];
		if(to.v==father){
			continue;
		}
		if(maxn<siz[to.v]){
			maxn=siz[to.v];
			num=to.v;
		}
	}
	for(int x=0;x<g[now].size();x++){
		node to=g[now][x];
		if(to.v==father){
			continue;
		}
		if(to.v==num){
			chain_top[to.v]=chain_top[now];
		}else{
			chain_top[to.v]=to.v;
		}
	}
	for(int x=0;x<g[now].size();x++){
		if(g[now][x].v==father){
			continue;
		}
		dfss(g[now][x].v,now);
	}
	return;
}

现在树剖完了, 就该 $LCA$ 了

树链剖分LCA

有两个节点 $A,B$ ,求它们最近公共祖先
$LCA$ 的大致思想就是不断地往上跳, 直到两个节点到根的路径成包含关系时停止. 但是这个往上跳的过程很费时间, 于是我们可以通过某些判断, 让节点往上跳一条重链的长度(如图)
这棵树是挺大的
假设现在我要求 $LCA(15,19)$ 以下是具体操作步骤

• 判断当前两个节点的链顶是不是同一个点
• 若是, 则输出两个点中深度小的那个
• 若不是, 就让链顶深度最大的那个点往上跳, 跳到链顶的父亲节点
• 重复上述过程, 直到判断为是

要是没太明白的话就自己手动模拟以下:

int LCA(int a,int b){
	while(ct[a]!=ct[b]){
		if(dep[chain_top[a]]>=dep[chain_top[b]]){
			a=fa[chain_top[a]];
		}else{
			b=fa[chain_top[b]];
		}
	}
	if(dep[a]<dep[b]){
		return a;
	}else{
		return b;
	}
}

个人认为这个比倍增 $LCA$ 好理解

例题

今天晚上更