看本博客前建议先看一下ST算法解决RMQ问题详解一，LCA概念最近公共祖先(LowestCommonAncestors,LCA)指有根树中距离两个节点最近的公共祖先。祖先指从当前节点到树根路径上的所有节点。u和v的公共祖先指一个节点既是u的祖先，又是v的祖先。u和v的最近公共.祖先指距离u和v最近的公共祖先。若v是u的祖先，则u和v的最近公共祖先是v。比如:二，解决方法暴力搜索法暴力搜索法有两种:向上标记法和同步前进法。1-1向上标记法从u向上一直到根节点，标记所有经过的节点;若v已被标记，则v节点为LCA(u,v);否则v也向上走，第1次遇到已标记的节点时，该节点为LCA(u,v)。1-2同

文章目录树形DP问题一、树的直径（二叉树==>一般树）[543.二叉树的直径](https://leetcode.cn/problems/diameter-of-binary-tree/)[124.二叉树中的最大路径和](https://leetcode.cn/problems/binary-tree-maximum-path-sum/)🎱(树的直径)[2246.相邻字符不同的最长路径](https://leetcode.cn/problems/longest-path-with-different-adjacent-characters/)二、树上最大独立集（打家劫舍Ⅲ）[337.打家劫舍I

今天讲最短路统计和分层图目录题目：LCA 思路：题目：最短路计数思路：题目：社交网络思路：题目：飞行路线 思路：题目：第二短路思路：                题目：LCA         思路：        非常明显了，之前就说过倍增迭代就是一个一个选区间使总长度达到M（凑一个数），用不大于它最大的二的次幂，减去之后，再重复这个过程。所以LCA+倍增逼近是最快的。                #include//最近公共祖先LCAP3379：给一棵数，求任意两点的LCAusingnamespacestd;constintmaxn=500002;intn,m,s,tot=0;inthe

文章目录lcaTarjan板子题：1172.祖孙询问lca或tarjan：1171.距离356.次小生成树352.闇の連鎖lcaO(mlogn)O(mlogn)O(mlogn)，n为节点数量，m为询问次数，lca是一种在线处理询问的算法自己也是自己的祖先倍增：fa(i,j)fa(i,j)fa(i,j)表示从i开始，向上走2j2^j2j步走到的点j=0，走到父节点j>0，分两步走，先走到2j−12^{j-1}2j−1步再走2j−12^{j-1}2j−1步，那么一共就会走2j2^j2j步，fa(i,j)=fa(fa(i,j−1),j−1)fa(i,j)=fa(fa(i,j-1),j-1)fa(i,

「观前提醒」「文章仅供学习和参考，如有问题请在评论区提出」目录前言定义性质求LCA倍增算法Trajan算法树链剖分基本概念基本性质具体实现参考资料前言简单的模板整理，只是概括了一下具体的实现方法（说到底是给自己写的），如果看不明白可以去看原视频（讲的很好），链接在参考资料里。定义最近公共祖先简称\(LCA\)（LowestCommonAncestor）。在一个树上，两个节点的最近公共祖先，就是这两个点的公共祖先里，离树根最远的那个。例如，\(6\)与\(8\)的最近公共祖先为\(1\)，\(5\)和\(3\)的最近公共祖先为\(5\)。性质\(u\)是\(v\)的祖先，当且仅当\(LCA(u,

一.LCA介绍LCA通常指的是“最近共同祖先”（LowestCommonAncestor）。LCA是一种用于解决树或图结构中两个节点的最低共同祖先的问题的算法。在树结构中，LCA是指两个节点的最近层级的共同祖先节点。例如，考虑一棵树，其中节点A是节点B和节点C的祖先，而节点D是节点B和节点C的共同祖先，但节点D不是最低层级的共同祖先。在这种情况下，LCA就是节点D。LCA算法在计算机科学中有广泛的应用，例如在计算树的最近公共祖先、解决图的连通性问题、计算有向无环图（DAG）的最近公共祖先等方面。常见的LCA算法包括基于深度优先搜索（DFS）的算法、基于倍增法的算法和Tarjan算法等。LCA算

最近公共祖先LCALCA（LeastCommonAncestors），即最近公共祖先，是指这样一个问题：在有根树中，找出某两个结点u和v最近的公共祖先（另一种说法，离树根最远的公共祖先）最近公共祖先是相对于两个节点来说的，一般来说，最近公共祖先为节点u和节点v的最近的公共祖先。若u为v的祖先或者v为u的祖先，则LCA(u,v)就是作为祖先的那个节点。示例图中86和67的LCA是75，61和85的LCA也是75。以下三种方法，后两种方法比较重要，需要熟记，再求后面次小生成树有很大帮助。LCA转RMQRMQ（RangeMinimum/MaximumQuery），即区间最值查询，是指这样一个问题：对

了解到一个quan新的东西：用ST表（欧拉序）实现LCA(树上最近公共祖先)欧拉序前序遍历得到的序列，叫dfs序但数字可以重复出现，一进一出，叫欧拉序会发现根结点总在中间而根结点是该段序列深度最小的点因此两个点的LCA，就是在该序列上两个点第一次出现的区间内深度最小的那个点即转化为区间RMQ问题，可以用ST表当然你可以再写一棵线段树（如果有修改操作）具体的，【笔记】dfs序，欧拉序，LCA的RMQ解法_dfs序求lca_Little_Fall的博客-CSDN博客