<=array_Node1_num;i++){ result=FindSource(array_Node2,array_Node1[i],0,array_Node2_num); if(result!=-1) break; } delete[]array_Node1; delete[]array_Node2; return result;}inline int CommonTree::Size(){ return size;}inline void CommonTree::getroot(int i){ root=i;}void CommonTree::Print()const{ for(inti=1;iTreeArray[i]<<""; cout<>NodeNum; int *AncestorTree=newint[NodeNum+1]; if(AncestorTree==NULL) exit(1); memset(AncestorTree,0,sizeof(int)*(NodeNum+1)); int father=1; for(intj=0;j>lop; for(inti=0;i>temp; AncestorTree[temp]=father; } father++; } for(j=1;j<=NodeNum;j++){ if (AncestorTree[j]==0){ AncestorTree[j]=j; break; } } int find_num; in>>find_num; int *result=newint[3*find_num]; if(result==NULL) exit(1); for(inti=0;i<2*find_num;i++) in>>result[i]; CommonTreemain_tree(10); main_tree.getdata(AncestorTree,NodeNum+1); main_tree.getroot(j); int displace=0; for(i=0;i 【最近公共祖先】C++代码实现：#include<iostream>#include<stdio.h>#include<memory.h>using namespace std;#definemax_size 1010int d[max_size],p[max_size][10];int head[max_size];int cnt;structEdge{ int v; int pre;}eg[max_size];//建树的函式void add(int x,int y){ eg[cnt].v=y; eg[cnt].pre=head[x]; head[x]=cnt++;}//dfs()初始整颗数 ， 算出d[1-n],p[1-n][j];void dfs(intk){ if (head[k]==0) return; int m,x,i,j; for(i=head[k];i!=0;i=eg[i].pre){ x=eg[i].v; p[x][0]=k; m=k; d[x]=d[k]+1; for(j=0;p[m][j]!=0;j++){ p[x][j+1]=p[m][j];//利用公式p[x][j]=p[p[x][j-1]][j-1],这里的m就是p[x][j-1]; m=p[m][j]; } dfs(x); }}int find_lca(int x,int y){ int m,k; if (x==y) return x; if(d[x]<d[y]){m=x;x=y;y=m;} m=d[x]-d[y]; k=0; while(m){//将x的深度调到和y的深度一样 if(m&1) x=p[x][k]; m>>=1; k++; } if (x==y)return x; k=0;//向上调节 ， 找最近公共祖先 ， 算法的核心 ， 相当于一个二分查找 。 while(x!=y){ if (p[x][k]!=p[y][k]||p[x][k]==p[y][k]&&k==0){//如果p[x][k]还不相等 ， 说明节点p[x][k]还在所求点的下面 ， 所以继续向上调节;如果相等了 ， 并且就是他们父节点 ， 则那个节点一定就是所求点 。 x=p[x][k]; y=p[y][k]; k++; } else k--;//如果p[x][k]=p[y][k],可以说明p[x][k]一定是x和y的共祖先 ， 但不一定是最近的,所以向下找看还有没有更近的公共祖先 } return x;}int main(){ int i,n,m,x,y; while(cin>>n>>m){ memset(head,0,sizeof(head)); memset(p,0,sizeof(p)); memset(d,0,sizeof(d)); cnt=1; for(i=2;i<=n;i++){ scanf("%d",&x); add(x,i); } dfs(1); for(i=0;i<m;i++){ scanf("%d%d",&x,&y); printf("%d/n",find_lca(x,y)); } } return 0;}
