[学习笔记]树链剖分(简易版) 及其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$ 好理解

例题

今天晚上更

原文地址：https://blog.csdn.net/Wangyd_525/article/details/142369355

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！