LCA就是最近公共祖先的意思，比如这个图 这个图中10 和 9 的最近公共祖先就是7 这个图中4 和10的最近公共祖先就是1 那么我们到底怎么来求最近公共祖先呢？
有两种方法来求最近公共祖先，1是倍增法，2是tarjan，这是一种离线算法，由于本人比较弱，所以只会第一种算法（主要是害怕弄混了，因为图的强连通分量里面会学另一个tarjan算法,还是自己比较弱）倍增法里面有一个很重要的数组f[x,k]，表示x往上跳 2 k 2^{k} 2k步所能够到达的点，拿上面的图举例子f[10,0] = 8,f[10,1] = 7,f[10,2] = 5···，再举一个例子f[9,0] = 7,f[9,1] = 6,f[9,2] = 1这里一个点往上跳 2 k 2^k 2k步不太好求，那么可以先跳 2 k − 1 2^{k - 1} 2k−1,然后再跳 2 k − 1 2^{k - 1} 2k−1，这样就相当于我们跳了 2 k 2^{k} 2k步假设t 是我们当前点跳了 2 k − 1 2^{k - 1} 2k−1，那么t = f[x,k - 1];f[x,k] = f[t,k - 1],也就是f[x][k] = f[f[x][k - 1]][k - 1];还有我们要算出根节点到每个点的距离，也就是每个点的深度，此时根节点的深度默认为1,depth[root] = 1;可以通过bfs或者dfs来预处理f数组 const int N = 4e4 + 10,M = N * 2; int h[N],e[M],ne[M],idx; int n,m; int root; int depth[N]; int f[N][19]; void add(int a,int b) { e[idx] = b,ne[idx] = h[a],h[a] = idx ++; } void dfs(int u) { for(int i = h[u];~i;i = ne[i]) { int j = e[i]; if(!depth[j]){ depth[j] = depth[u] + 1; /* 下面是重点，其实下面这个16是通过求log(n)，算出来的，也就是我们最多 会跳2^15步数，具体题目具体分析一般写大一点肯定没问题，别超过20； */ f[j][0] = u; for(int k = 1;k < 16;k ++) { int t = f[j][k - 1]; f[j][k] = f[t][k - 1]; } dfs(j); } } } 那么f数组预处理出来了，那么下面就是查找最近公共祖先的技巧了首先是把让x跳到和y一层（默认x比y的深度深，如果x比较浅的话，swap(x,y)）跳到和y同一层，假设我们x需要跳z步数才能和y一层，由于任何一个数都可以被拆分成很多2的不同次幂加起来，所以我们就从2的最高次幂（也就是15）开始往上跳，如果跳到一个点p，depth[p] >= depth[y]，那么我们还是可以继续往上跳···假设此时我们已经跳到了和y同一层，那么我们让x，y往上跳相同的步数，让他们跳到其公共祖先的下面一个节点，注意此时的这个节点可能相同，也可能不同，但是这个节点再往上跳一步肯定是相同的，比如3和9的最近公共祖先是1，而我们只会跳到2号节点和5号节点，只需要这个节点再往上跳一下就到达了最近公共祖先节点至于为什么不直接跳到最近公共祖先节点呢？我画一个图假设3和4往上跳，那么他们最先跳到1号节点，而1号节点并不是它们的最近公共祖先，2号节点才是，所以我们跳到最近公共祖先的下一个节点 int lca(int a,int b) { // a的深度比b浅 if(depth[a] < depth[b]){ swap(a,b); } // 把a跳到和b同一层 for(int i = 15;i >= 0;i --) { if(depth[f[a][i]] >= depth[b]){ a = f[a][i]; } } if(a == b) return a; // 下面是a和b同时往上跳，注意此时a和b是在同一层的，同一层，同一层，三遍~~~~~~ for(int i = 15;i >= 0;i --) { if(f[a][i] != f[b][i]) { a = f[a][i],b = f[b][i]; } } return f[a][0]; }哪里不对希望大佬批评指正，或者哪里不理解可以私信问我
