其實看了LCA已經有好幾天了就是沒做題，今天找了這道題，最近樹的最近公共祖先，想好好看看圖論的，幸好隊裡買了些書，就看到這個算法的很簡單就是一個深度遍歷的過程。如果想更深入有了解的話推薦博客http://dongxicheng.org/structure/lca-rmq/
這種離線算法很合適很多詢問的題目，這道題只有一個詢問。所以我設置了一個success標志，只要找到答案就可以結束了。
代碼：
[cpp]
#include<iostream>
#include<string.h>
using namespace std;
int size,a,b,ret,f[10050],head[10050];
bool visit[10050],success;
struct Edge
{
int v,next;
} e[10050];
int Find(int x) //並查集
{
if( x!=f[x])
f[x]=Find(f[x]);
return f[x];
}
void LCA(int u)
{
visit[u]=true;
f[u]=u;
for(int i=head[u]; i!=-1&&!success; i=e[i].next){
// printf("%d %d\n",u,e[i].v);
if( !visit[e[i].v]){
LCA(e[i].v);
f[e[i].v]=u;
}
}
if( u==a&&visit[b]){// 因為樹遍歷的順序不確定，尋找a,b和尋找b,a是一樣的。
ret=Find(b);
success=true;
}
if( u==b&&visit[a]){
ret=Find(a);
success=true;
}
}
int main()
{
int t,n,i;
scanf("%d",&t);
while( t--){
scanf("%d",&n);
memset(head,-1,sizeof(head));
memset(f,0,sizeof(f));
memset(visit,true,sizeof(visit));
size=0;
for( i=1; i<n; i++){
scanf("%d%d",&a,&b);
visit[b]=false; //方便找到樹的根節點，根節點是沒有父親結點的所以不可能作為孩子出現。
e[size].v=b;
e[size].next=head[a];
head[a]=size++;
}
scanf("%d%d",&a,&b);
if( a==b)
printf("%d\n",a);
else{
for( i=1; i<=n; i++)//尋找根節點
if( visit[i])
break;
success=false;
memset(visit,false,sizeof(visit));
// printf("%d\n",i);
LCA(i);
printf("%d\n",ret);
}
}
return 0;
}
作者：aacm1992
