【POJ1330】Nearest Common Ancestors-LCA算法

题目大意：给定一棵有N个节点的有根树，对于每条边，读入两个数，标号为前面那个数的点是标号为后面那个数的点的父亲，在每组测试数据的最后给出两个点，求出它们的最近公共祖先（LCA）。

做法：LCA裸题......也可以用倍增写，但是鉴于本人比较懒的缘故，当然是怎么能过就怎么写啦。

以下是本人代码（Tarjan）：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int T,n,a,b,tot,first[10010],qa,qb,ans,f[10010],fa[10010],root;
bool vis[10010];
struct {int v,next;} e[20010];

void insert(int a,int b)
{
  e[++tot].v=b;
  e[tot].next=first[a];
  first[a]=tot;
}

int find(int x)
{
  int r=x,i=x,j;
  while(r!=f[r]) r=f[r];
  while(i!=r) {j=f[i];f[i]=r;i=j;}
  return r;
}

void merge(int a,int b)
{
  f[find(a)]=find(b);
}

void tarjan(int v)
{
  f[v]=v;
  for(int i=first[v];i;i=e[i].next)
    if (e[i].v!=fa[v])
	  tarjan(e[i].v);
  vis[v]=1;
  if (v==qa&&vis[qb]) ans=find(qb);
  if (v==qb&&vis[qa]) ans=find(qa);
  merge(v,fa[v]);
}

int main()
{
  scanf("%d",&T);
  while(T>0)
  {
    scanf("%d",&n);
	memset(first,0,sizeof(first));
	memset(vis,0,sizeof(vis));
	memset(fa,0,sizeof(fa));
	tot=0;
	for(int i=1;i<n;i++)
	{
	  int a,b;
	  scanf("%d%d",&a,&b);
	  insert(a,b);insert(b,a);
	  fa[b]=a;
	}
	root=1;
	while(fa[root]!=0) root=fa[root];
	scanf("%d%d",&qa,&qb);
	tarjan(root);
	printf("%d
",ans);
    T--;
  }
  
  return 0;
}