最近公共祖先，Targin算法
Tarjan算法基于深度优先搜索的框架，对于新搜索到的一个结点，首先创建由这个结点构成的集合，再对当前结点的每一个子树进行搜索，每搜索完一棵子树，则可确定子树内的LCA询问都已解决。其他的LCA询问的结果必然在这个子树之外，这时把子树所形成的集合与当前结点的集合合并，并将当前结点设为这个集合的祖先。之后继续搜索下一棵子树，直到当前结点的所有子树搜索完。这时把当前结点也设为已被检查过的，同时可以处理有关当前结点的LCA询问，如果有一个从当前结点到结点v的询问，且v已被检查过，则由于进行的是深度优先搜索，当前结点与v的最近公共祖先一定还没有被检查，而这个最近公共祖先的包涵v的子树一定已经搜索过了，那么这个最近公共祖先一定是v所在集合的祖先。
AC代码：
#include<iostream>#include<cstdio>#include<string.h>#define CLR(arr,val) memset(arr,val,sizeof(arr))#define N 10005using namespace std;typedef struct str{int num;int Next;}Node;Node s[2*N];int head[N];int Father[N];bool vis[N];int in[N];int res=0;int p,q;void init(){res=0;CLR(head,-1);CLR(vis,false);CLR(in,0); for(int i=1;i<=N;++i) Father[i]=i;}void add(int a,int b){s[res].num=b;s[res].Next=head[a];head[a]=res++;}int Find(int x){if(x==Father[x]) return x;return Father[x]=Find(Father[x]);}void Union(int x,int y){int a=Find(x);int b=Find(y);if(a!=b) Father[a]=b;}void _LCA(int x){for(int i=head[x];i!=-1;i=s[i].Next){_LCA(s[i].num);Union(s[i].num,x);}vis[x]=true;if(x==p&&vis[q]){printf("%d\n",Find(q));return;}if(x==q&&vis[p]){printf("%d\n",Find(p));return;}}int main(){int T;scanf("%d",&T);while(T--){init();int n,i;scanf("%d",&n);for( i=1;i<n;++i){int a,b;scanf("%d%d",&a,&b);add(a,b);in[b]++;}scanf("%d%d",&p,&q);for(i=1;in[i];i++);_LCA(i);}return 0;}