最近の公衆祖先(LCA)

/********************************************************************
 ** @file    nuaa1025.cpp
 ** @date    Fri Apr 29 22:33:37 2011
 ** @brief           ,             
 **     
 ********************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX  100002
int fa[MAX];
int depth[MAX];
/*  node     */
int getDepth(int node){
  if(fa[node]==0)return 1;/*      */
  /*        ,                 */
  else if(depth[node]==-1)return depth[node]=getDepth(fa[node])+1; 
  /*      ,    */
  else return depth[node];
}
int LCA(int a,int b){
  getDepth(a);getDepth(b);
/*           */
  while(depth[a]<depth[b])b=fa[b];
  while(depth[b]<depth[a])a=fa[a];
  while(a!=b){
    a=fa[a];//       ，    
    b=fa[b];
  }return a;
}
int main(int argc, char *argv[])
{
  memset(depth,-1,sizeof(depth));
  int n,m;int num;
  scanf("%d",&n);
  for(int i=1;i<=n;++i){
    scanf("%d",&fa[i]);
  }
  scanf("%d",&m);
  int u,v;
  for(int i=0;i<m;++i){
    scanf("%d%d",&u,&v);
    printf("%d/n",LCA(u,v));
  }
  return 0;
}

/********************************************************************
 ** @file    poj1330.cpp
 ** @date    Fri Apr 29 15:34:08 2011
 ** @brief   
 **          LCA:Tarjan  
      LCA   Tarjan    [  ]
             ，      LCA   O(n+Q)  ，  Q    
   。
Tarjan             ，           ，         
     ，                ，        ，      
  LCA      。   LCA              ，       
              ，               。       
    ，              。                ， 
            LCA  ，             v   ， v  
   ，             ，     v              
 ，            v           ，            
 v       。
 ********************************************************************/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
#define MAX 10001
int indegree[MAX];/*        */
vector<int>tree[MAX];/*     */
vector<int>Que[MAX];
int ancestor[MAX];
int f[MAX];
bool vis[MAX];
void init(int n){/*   */
  memset(indegree,0,sizeof(indegree));
  memset(vis,false,sizeof(vis));
  for(int i=0;i<n;++i){
    f[i]=i;ancestor[i]=0;
    tree[i].clear();
    Que[i].clear();
  }
}
void input(int n){
  int a,b;
  for(int i=1;i<n;++i){
    scanf("%d%d",&a,&b);
    tree[a].push_back(b);
    indegree[b]++;
  }
    scanf("%d%d",&a,&b);
    Que[a].push_back(b);
    Que[b].push_back(a);
}
int find(int u){
  if(u==f[u])return u;
  else return f[u]=find(f[u]);
}
bool unin(int x,int y){/*      true     false*/
  int a=find(x);int b=find(y);
  if(a==b)return false;
  else f[a]=b;
  return true;
}
void LCA(int u){
  ancestor[u]=u;
  for(int i=0;i<tree[u].size();++i){
    LCA(tree[u][i]);
    unin(u,tree[u][i]);
    ancestor[find(u)]=u;
  }
  vis[u]=true;
  for(int i=0;i<Que[u].size();++i){
    if(vis[Que[u][i]]){
      cout<<ancestor[find(Que[u][i])]<<endl;
      return;
    }
  }
}
int main(int argc, char *argv[])
{
  int n,t;
  cin>>t;
  for(int i=0;i<t;++i) {
    cin>>n;
    init(n);
    input(n);
    int u;
    for(int i=1;i<n;++i)
      if(indegree[i]==0){
        u=i;break;
      }
    LCA(u);
  }
  return 0;
}