树链剖分，指一种对树进行划分的算法，它先通过轻重边剖分将树分为多条链，保证每个点属于且只属于一条链，然后再通过数据结构（树状数组、SBT、SPLAY、线段树等）来维护每一条链。

具体步骤：

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

第一遍dfs求出树每个结点的深度deep[x]，其为根的子树大小size[x]，以及每个点的父亲fa[x]。

第二遍dfs以根节点为起点，先dfs其儿子中size最大的儿子，相当于重边，之后dfs其它轻儿子。

在dfs的过程中求出每个节点的dfs序以及沿着重链向根最远到达哪个点，每条重链的dfs序就相当于一段区间，树上问题转化为区间问题。

根据不同题目使用维护区间的数据结构即可。

（以上摘自lyd课件）

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄