概况
LCA(Lowest Common Ancestors),即最近公共祖先,是指在有根树中,找出某两个结点u和v最近的公共祖先。
实现过程 预处理:通过dfs遍历,记录每个节点到根节点的距离dist[u],深度d[u] init()求出树上每个节点u的2^i祖先p[u][i] 求最近公共祖先,根据两个节点的的深度,如不同,向上调整深度大的节点,使得两个节点在同一层上,如果正好是祖先结束,否则,将两个节点同时上移,查询最近公共祖先。 代码:#include<bits/stdc++.h> #include<queue> using namespace std; const int N=5e5+5; int n,m,s; int root; int idx=1; int ver[2*N],nex[2*N],head[2*N],dis[2*N],f[2*N][25]; queue<int>q; int t; void add(int x,int y) {//邻接表建图 ver[++idx]=y; nex[idx]=head[x]; head[x]=idx; return ; } void bfs() {//bfs会比dfs更加保险 q.push(root); dis[root]=1;//根节点的深度为1 while(!q.empty()) { int x=q.front(); q.pop(); for(int i=head[x]; i; i=nex[i]) {//向下一层搜索 int y=ver[i]; if(dis[y]) continue;//防止死循环 dis[y]=dis[x]+1;//深度更新 f[y][0]=x;//2^0=1,即为y的父结点 for(int j=1; j<=t; j++) { f[y][j]=f[f[y][j-1]][j-1];//更新2^i个祖先 } q.push(y); } } return ; } int lca(int x,int y) { if(dis[x]<dis[y]){//严格规范dis[x]>dis[y] swap(x,y); } for(int i=t; i>=0; i--) { if(dis[f[x][i]]>=dis[y]) x=f[x][i];//使x和y的深度相同 } if(x==y) return x;//已经相同,则直接返回x for(int i=t; i>=0; i--) { if(f[x][i]!=f[y][i]) {//如果第2^i个祖先不相同,说明还没有到最小公共祖先 x=f[x][i]; y=f[y][i];//更新x,y } } return f[x][0];//返回x的父节点——即最小公共祖先 } int main() { cin>>n; t=(log(n)/log(2))+1; for(int i=1; i<=n; i++) { int a,b; cin>>a>>b; if(b==-1) root=a; add(a,b); add(b,a); } bfs(); cin>>m; for(int i=1; i<=m; i++) { int x,y; cin>>x>>y; if(lca(x,y)==x) cout<<1<<endl; if(lca(x,y)==y) cout<<2<<endl; if(lca(x,y)!=x&&lca(x,y)!=y) cout<<0<<endl; } // for(int i=1;i<=5;i++)cout<<i<<":"<<dis[i]<<endl; return 0; }