方法1.标记法1将u到根节点的路径标记一遍2将v到根节点的路径走一遍如果与u标记的路径相重合则重合点为两者公共祖先2.跳跃法(1)先让其中一个节点跳到另一个的同一深度(2)两个一起跳直到找到共同祖先代码如下vectorint g[500010]; //存节点 int d[500010]; //节点深度 int f[500010]; //节点父亲 void dfs(int u,int fa){ //计算节点深度和父节点 d[u]d[fa]1; f[u]fa; for(int i0;ig[u].size();i){ int vg[u][i]; if(vfa){ continue; } dfs(v,u); } } int lca(int u,int v){ if(d[u]d[v]){ //保证u最深 swap(u,v); } int chad[u]-d[v]; for(int i1;icha;i){ //保证让两个节点在同一深度 uf[u]; } while(u!v){ //两个节点同时向上爬 uf[u]; vf[v]; } return u; //此时u和v就都是他俩的公共祖先 }(3)利用二进制优化跳跃的过程状态father[i][j]表示以i开始长度为2^j的父亲模板题P3379 P3379 【模板】最近公共祖先LCA - 洛谷程序模板#includebits/stdc.h using namespace std; int n,m,s; vectorint g[500010]; int d[500010]; int father[500010][25]; void dfs(int u,int fa,int depth){ father[u][0]fa; for(int i1;i20;i){ father[u][i]father[father[u][i-1]][i-1]; } d[u]depth; for(int i0;ig[u].size();i){ int vg[u][i]; if(vfa) continue; dfs(v,u,depth1); } } int lca(int a,int b){ if(d[a]d[b]){ swap(a,b); } for(int k20;k0;k--){ if(d[father[a][k]]d[b]){ afather[a][k]; } } if(ab){ return a; } for(int k20;k0;k--){ if(father[a][k]!father[b][k]){ afather[a][k]; bfather[b][k]; } } return father[a][0]; } int main(){ cinnms; for(int i1;in;i){ int x,y; cinxy; g[x].push_back(y); g[y].push_back(x); } dfs(s,0,1); while(m--){ int a,b; cinab; coutlca(a,b)endl; } return 0; }感谢观看