视频字幕
树链剖分是一种重要的树上数据结构技术。它的核心思想是将树分解为若干条链，通过重儿子和轻儿子的概念来实现。对于每个节点，我们选择子树大小最大的儿子作为重儿子，其他儿子称为轻儿子。连接父节点和重儿子的边叫重边，用红色表示；连接父节点和轻儿子的边叫轻边，用灰色表示。这样的划分为后续的LCA查询奠定了基础。
现在我们来看重链的划分过程。从根节点1开始，它的重儿子是节点2，所以形成第一条重链。节点2的重儿子是节点5，继续延伸重链1。节点3有两个儿子，子树大小相同，我们选择节点6作为重儿子，形成重链2。节点7形成重链3。节点4是叶子节点，单独成链。这样整棵树被划分为4条重链。重要的是，任意两点间的路径最多经过对数级别的重链，这保证了查询的高效性。
DFS序与链顶标记是树链剖分的关键预处理步骤。第一次DFS从根节点开始，计算每个节点的深度、子树大小、父节点和重儿子信息。第二次DFS进行链剖分，为每个节点标记其所在重链的链顶。我们可以看到，节点1、2、5在同一条重链上，它们的链顶都是1。节点3、6在一条重链上，链顶是3。节点4和7各自单独成链。DFS序记录了遍历的顺序，这对后续的区间操作很重要。
现在演示LCA查询算法的具体过程。假设我们要查询节点4和节点6的最近公共祖先。首先检查它们是否在同一条重链上，节点4的链顶是4，节点6的链顶是3，不在同一链上。接下来，我们让深度更大的链顶向上跳跃。节点4跳到父节点2，现在比较节点2和节点6，它们的链顶分别是1和3，仍不在同一链上。继续让节点6跳到父节点3，再让节点3跳到父节点1。最终节点2和节点1在同一条重链上，返回深度较小的节点1作为LCA。整个过程时间复杂度为O(log n)。