MhxMa 的最近公共祖先 (LCA) 练习题

本题单主要针对最近公共祖先(LCA)问题。LCA 问题可以通过朴素算法、倍增法、tarjan 等算法解决。

最近公共祖先简称 LCA(Lowest Common Ancestor)。两个节点的最近公共祖先,就是这两个点的公共祖先里面,离根最远的那个。

LCA 算法是一种常见的树上算法,oi-wiki 上有详细的讲解,可自行观看。LCA 算法经常与一下算法搭配使用,例如树链剖分、线段树等。

本题单难度在 普及~提高+ 之间。本题单适合培养 LCA 算法从入门到进阶到熟练运用的过程,同时建议按照题单顺序来完成,也可以通过自身学习情况来决定自己的做题顺序。

建议的前置知识:线段树、树链剖分、树上前缀和差分。


  1. P3379 - 【模板】最近公共祖先(LCA)
  2. P1351 - [NOIP 2014 提高组] 联合权值
  3. P5836 - [USACO19DEC] Milk Visits S
  4. P10113 - [GESP202312 八级] 大量的工作沟通
  5. P4427 - [BJOI2018] 求和
  6. P5002 - 专心OI - 找祖先
  7. P3128 - [USACO15DEC] Max Flow P
  8. P8805 - [蓝桥杯 2022 国 B] 机房
  9. P6869 - [COCI 2019/2020 #5] Putovanje
  10. P8972 - 『GROI-R1』 一切都已过去
  11. P4281 - [AHOI2008] 紧急集合 / 聚会
  12. P8025 - [ONTAK2015] Związek Harcerstwa Bajtockiego
  13. P9433 - [NAPC-#1] Stage5 - Conveyors
  14. P1852 - [国家集训队] 跳跳棋
  15. P1967 - [NOIP 2013 提高组] 货车运输
  16. P4180 - [BJWC2010] 严格次小生成树