[LCA入门]——看这一张图就够了 by Apare_xzc
分类:
文章
•
2024-05-13 08:40:10
[LCA入门]——看这一张图就够了
Apare_xzc 2020.1.30
LCA:最近公共祖先全称为Lowest Common Ancestors,求一棵树上两个结点最近的公共祖先
RMQ:可以区间查询最大或最小值,预处理ST表,可以O(1)查询
欧拉序:即为对树进行先序遍历,按顺序记录遍历中经过的所有结点(包括回溯时经过的)
LCA的一些用途:求树上两点之间的最短距离…
我画了一上午的图:
![[LCA入门]——看这一张图就够了 by Apare_xzc [LCA入门]——看这一张图就够了 by Apare_xzc](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzM1LzdjYjQwYTU3Mzk3MDU1YTFhZDFlNDQxYTIxYTVjYjViLnBuZw==)
其实是给npy画的,画了一上午,眼睛疼,希望可以感动她,反正我自己是感动了…
求LCA的几种方法:
相信你认真看了这幅图,LCA一定就入门啦
附:我做过的写了题解的关于LCA的题