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

例题

今天晚上更