模板题P3379 【模板】最近公共祖先LCA最近公共祖先是求两个点在一颗树上的公共祖先。倍增法在找祖先之前要进行处理在 DFS 中完成操作根节点的父亲设置为虚点记录他们的祖先以及深度。定义是点i往上的第个点则即点i上的第个点这个点再向上找个点(在推点之前以上的点已经全部推完)代码for(int j 1;j20;j){ f[i][j] f[f[i][j-1]][j-1]; }接着找点的子节点推。输入两个点 A 和 B。 开始找公共祖先之后需要先对齐点A和点B使它们的深度相同。将比较小的点设置为A点从开始找祖先的深度统一20如果那个祖先的深度比 B 点深或相等即则将自己赋值为此祖先。代码for(int i 20;i0;i--){ if(d[f[a][i]]d[b]){ a f[a][i]; } }当点 A 和点 B 深度相同时先判断一下它们俩是否相等如果相等则代表公共祖先是A。不相等找公共祖先。如果 A 和 B 的祖先同时向上找相同个数不相等则他们的公共祖先在这个数之上将 A 和 B 赋值为它们的祖先随后继续找。如相等则跳过找更低一层的。如果在某一层没找到相同祖先则他的祖先必定在它上面第到之间。代码for(int i 20;i0;i--){ if(f[a][i]!f[b][i]){ a f[a][i],b f[b][i]; } }返回结果就是找到目标的上一层即return f[a][0];全文代码#includebits/stdc.h using namespace std; const int N 5e510; int n,m,s,d[N],f[N][21]; vectorint g[N]; void dfs(int i,int fa){ f[i][0] fa; d[i] d[fa]1; for(int j 1;j20;j){ f[i][j] f[f[i][j-1]][j-1]; } for(int x:g[i]){ if(x!fa){ dfs(x,i); } } } int LCA(int a,int b){ if(d[a]d[b]){ swap(a,b); } for(int i 20;i0;i--){ if(d[f[a][i]]d[b]){ a f[a][i]; } } if(ab){ return a; } for(int i 20;i0;i--){ if(f[a][i]!f[b][i]){ a f[a][i],b f[b][i]; } } return f[a][0]; } int main(){ scanf(%d%d%d,n,m,s); for(int i 1;in;i){ int a,b; scanf(%d%d,a,b); g[a].push_back(b); g[b].push_back(a); } dfs(s,0); while(m--){ int a,b; scanf(%d%d,a,b); printf(%d\n,LCA(a,b)); } return 0;