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

[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 <–

全部评论

相关推荐

10-27 17:26
东北大学 Java
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务