树链剖分（HLD）是省选必考算法。

树链剖分解决什么问题

  • 树上路径查询
  • 树上路径修改
  • 子树查询 / 修改

核心概念

  • 重儿子：子树最大的儿子
  • 轻儿子：非重儿子
  • 重链：从根到重儿子的链
  • dfs 序：树链剖分的编号

两个 dfs

dfs1：求子树大小和重儿子

dfs2：剖分树链，分配 dfs 序

常见应用

  • LCA（最近公共祖先）
  • 树上路径和
  • 树上路径最大值
  • 子树和

学习建议

  • 先掌握 LCA
  • 再学路径查询
  • 配合线段树使用

省选一对一辅导：151 6522 2880