poj1330 Nearest Common Ancestors

時間復雜度分析：找父節點集合O(n)，排序O(nlogn)，二分O(logn)，二分次數不超過n/2次，因此算法復雜度是O（nlogn）   代碼： [cpp]  #include<iostream>   #include<algorithm>   #include<cstring>   using namespace std;      int p[10008],pa[10008],pb[10008];      void getFa(int x,int &n,int *f){       n=0;       f[n++]=x;       while(p[x]){//直到找到根節點，p[x]=0表x為樹根           x=p[x];           f[n++]=x;       }   }   //二分搜索   int binarySearch(int e,int *a,int n){       int l=0,h=n-1,mid;       while(l<=h){           mid=(l+h)/2;           if(a[mid]==e)return e;           if(a[mid]>e) h=mid-1;           else l=mid+1;       }       return -1;   }   //找最近共同祖先   int findMCA(int a,int b,int na,int nb){       if(a==b) return a;       if(na>nb){//b可能是a祖先，所以用b的祖先“由近及遠”地判斷是否為a的祖先，下同           sort(pa,pa+na);           for(int i=0;i<nb;i++){               int tmp=binarySearch(pb[i],pa,na);               if(tmp!=-1)return tmp;           }       }       else{           sort(pb,pb+nb);           for(int i=0;i<na;i++){               int tmp=binarySearch(pa[i],pb,nb);               if(tmp!=-1)return tmp;           }       }   }      int main(){       int n,t,pat,son;       int a,b,na,nb;       cin>>t;       while(t--){           cin>>n;           memset(p+1,0,sizeof(int)*n);           for(int i=1;i<n;i++){               cin>>pat>>son;               p[son]=pat;           }           cin>>a>>b;           //分別記錄a,b的所有祖先           getFa(a,na,pa);           getFa(b,nb,pb);           //找出最近共同祖先           cout<<findMCA(a,b,na,nb)<<endl;       }       return 0;   }