最近公共祖先问题，求的是中两个节点的最近公共祖先。使用了一个带并查集的离线算法。
#include <stdio.h>

const int LEN = 10005;

int p[LEN];

void make ( int n )
{
    
    for ( int i=0; i<n; i++ )
    {
        p[i] = -1;
    }
}

int find ( int a )
{

    if ( p[a] < 0 )
    {
        return a;
    }
    int r = find ( p[a] );
    p[a] = r;

    return r;
}

void un ( int a, int b )
{

    int ra = find ( a );
    int rb = find ( b );

    p[rb] = ra;
}

struct
{
    int c;/*记录结点的入度*/
    int last;/*记录最后一个节点的地址*/
    int next;
}tab[LEN];/*邻接链表头,记录最后一个节点的地址*/
typedef struct
{
    int num;
    int next;
}type;
type node[LEN*2];
int next1; /*下一个可以使用的位置*/

void initm ( int n )
{

    next1 = 0;
    for ( int i=0; i<n; i++ )
    {
        tab[i].c = 0;
        tab[i].last = -1;
        tab[i].next = -1;
    }
}

void adde ( int b, int e )/*增加一条边*/
{

    node[next1].num = e;
    node[next1].next = -1;
    if ( tab[b].next >= 0 )
    {
        node[ tab[b].last ].next = next1;
    }
    else
    {
        tab[b].next = next1;
    }
    tab[b].last = next1;
    tab[e].c ++;
    next1 ++;
}

struct
{
    int next;
    int last;
}que[LEN];
type q[LEN*2];
int next2;

void initq ( int n )
{

    next2 = 0;
    for ( int i=0; i<n; i++ )
    {
        que[i].last = -1;
        que[i].next = -1;
    }
}

void addq ( int b, int e )/*增加一条边*/
{

    q[next2].num = e;
    q[next2].next = -1;
    if ( que[b].next >= 0 )
    {
        q[ que[b].last ].next = next2;
    }
    else
    {
        que[b].next = next2;
    }
    que[b].last = next2;
    next2 ++;
}

int color[LEN];

void initc ( int n )
{

    for ( int i=0; i<n; i++ )
    {
        color[i] = 0;
    }
}

void lca ( int p )
{

    for ( int i=tab[p].next; i!=-1; i=node[i].next )
    {
        lca ( node[i].num );
        un ( p, node[i].num );
    }

    for ( i=que[p].next; i!=-1; i=q[i].next )
    {
        if ( color[ q[i].num ] )
        {
            printf ( "%d\n", find ( q[i].num ) + 1 );
        }
    }
    color[p] = 1;
}

int main ()
{

    int t;
    int n;
    int b, e;

    scanf ( "%d", &t );
    while (  t -- )
    {
        scanf ( "%d", &n );

        initm ( n );
        for ( int i=0; i<n-1; i++ )
        {
            scanf ( "%d%d", &b, &e );
            adde ( b-1, e-1 );
        }

        initq ( n );
        scanf ( "%d%d", &b, &e );
        addq ( b-1, e-1 );
        addq ( e-1, b-1 );

        initc ( n );/*初始化颜色*/
        make ( n );

        for ( i=0; i<n; i++ )
        {
            if ( ! tab[i].c )
            {
                break;
            }
        }
        lca ( i );

    }
    return 0;
}
地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1330