#include<iostream>
using namespace std;
int tree[10001][100],in[10001],p[10001];
int cas,s,t;
int n,Q1,Q2;
bool v[10001];
void Make_Set(int t)
{
    p[t]=t;
}
int Find_Set(int t)
{
    if(t!=p[t])
    {
        p[t]=Find_Set(p[t]);
    }
    return p[t];
}
void Union(int u,int v)
{
    p[v]=u;
}
int LCA(int u)
{
    Make_Set(u);
    int i;
    for(i=1;i<=tree[u][0];i++)
    {
        LCA(tree[u][i]);
        Union(u,tree[u][i]);
    }
    v[u]=1;
    if(u==Q1&&v[Q2])
    {
        printf("%d\n",p[Find_Set(Q2)]);
    }
    else if(u==Q2&&v[Q1])
    {
        printf("%d\n",p[Find_Set(Q1)]);
    }
    return 0;
}
int main()
{
    scanf("%d",&cas);
    while(cas--)
    {
        int i;
        memset(tree,0,sizeof(tree));
        memset(in,0,sizeof(in));
        memset(v,0,sizeof(v));
        scanf("%d",&n);
        for(i=1;i<n;i++)
        {
            scanf("%d%d",&s,&t);
            tree[s][++tree[s][0]]=t;
            in[t]++;
        }
        scanf("%d%d",&Q1,&Q2);
        for(i=1;i<=n;i++)
        {
            if(in[i]==0)
                break;
        }
        LCA(i);
    }
    system("pause");
    return 0;
}
Tarjan算法基于深度优先搜索的框架，对于新搜索到的一个结点，首先创建由这个结点构成的集合，再对当前结点的每一个子树进行搜索，每搜索完一棵子树，则可确定子树内的LCA询问都已解决。其他的LCA询问的结果必然在这个子树之外，这时把子树所形成的集合与当前结点的集合合并，并将当前结点设为这个集合的祖先。之后继续搜索下一棵子树，直到当前结点的所有子树搜索完。这时把当前结点也设为已被检查过的，同时可以处理有关当前结点的LCA询问，如果有一个从当前结点到结点v的询问，且v已被检查过，则由于进行的是深度优先搜索，当前结点与v的最近公共祖先一定还没有被检查，而这个最近公共祖先的包涵v的子树一定已经搜索过了，那么这个最近公共祖先一定是v所在集合的祖先。
贴一个地址吧：http://yinyifan.com/blog/2008/11/lowest_common_ancester_tarjan_alogrithm