LCA——ST表+欧拉序

了解到一个quan新的东西：

用ST表（欧拉序）实现LCA(树上最近公共祖先)

欧拉序

前序遍历得到的序列，叫dfs序
但数字可以重复出现，一进一出，叫欧拉序
会发现根结点总在中间
而根结点是该段序列深度最小的点
因此两个点的LCA，
就是在该序列上两个点第一次出现的区间内深度最小的那个点

即转化为区间RMQ问题，可以用ST表
当然你可以再写一棵线段树（如果有修改操作）

具体的，【笔记】dfs序，欧拉序，LCA的RMQ解法_dfs序求lca_Little_Fall的博客-CSDN博客

本栏目推荐文章
• LCA
• lca 学习笔记
• st表lca
• 【学习笔记】浅谈 RMQ 与 LCA
• 最近公共祖先模板(LCA)
• 树链剖分——最近公共祖先（LCA）
• P3379 【模板】最近公共祖先（LCA）
• 倍增LCA
• 最近公共祖先(LCA)
• 11.21学习小结 //LCA

LCA笔记lca 算法lca 祖先lca 方法lca 祖先 模板lca binary 1151 tree lca leetcode tarjan 341 lca 性质lca 三个 技术pca lca p4211 2014 lnoi lca