[LCA入门]——看这一张图就够了

Apare_xzc 2020.1.30

LCA：最近公共祖先全称为Lowest Common Ancestors，求一棵树上两个结点最近的公共祖先

RMQ：可以区间查询最大或最小值，预处理ST表，可以O(1)查询

欧拉序：即为对树进行先序遍历，按顺序记录遍历中经过的所有结点(包括回溯时经过的)

LCA的一些用途：求树上两点之间的最短距离…

我画了一上午的图:

其实是给npy画的，画了一上午，眼睛疼，希望可以感动她，反正我自己是感动了…

求LCA的几种方法：

  • 倍增

  • dfs欧拉序+RMQ预处理

  • tarjan

相信你认真看了这幅图，LCA一定就入门啦

附：我做过的写了题解的关于LCA的题

HDU2586(LCA)解题报告 Apare_xzc（模板题）<–
【CCF 201909-5】城市规划(LCA+暴力全排列40 & 树形dp100) Apare_xzc <–