POJ 1330 Nearest Common Ancestors

笔者的离线LCA模板。这里并查集和dfs的使用是个妙招。

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxv 10005
#define maxe 20005
#define maxq 105
using namespace std;
struct edge
{
int v,nxt;
}e[maxe];
struct question
{
int qq,nxt;
int index;
}q[maxq];
int t,g[maxv]={0},h[maxv]={0},n,nume,ans[maxq]={0},numq,father[maxv];
int ancestor[maxv];
bool flag[maxv]={false},vis[maxv]={false};
void addedge(int u,int v)
{
e[++nume].v=v;
e[nume].nxt=g[u];
g[u]=nume;
}
void addquery(int u,int v,int index)
{
q[++numq].qq=v;
q[numq].nxt=h[u];
q[numq].index=index;
h[u]=numq;
}
int getfather(int x)
{
if (x!=father[x])
father[x]=getfather(father[x]);
return father[x];
}
void unionn(int x,int y)
{
int r1=getfather(x),r2=getfather(y);
if (r1!=r2)
father[r1]=r2;
}
void lca(int u)
{
vis[u]=true;
ancestor[u]=u;
for (int i=g[u];i;i=e[i].nxt)
{
if (vis[e[i].v]==true)
continue;
lca(e[i].v);
unionn(u,e[i].v);
ancestor[getfather(u)]=u;
}
for (int i=h[u];i;i=q[i].nxt)
{
int v=q[i].qq;
if (vis[v]==true)
ans[q[i].index]=ancestor[getfather(v)];
}
}
void work()
{
nume=0;numq=0;
memset(g,0,sizeof(g));
memset(h,0,sizeof(h));
memset(ans,0,sizeof(ans));
memset(vis,false,sizeof(vis));
memset(flag,false,sizeof(flag));
memset(ancestor,0,sizeof(ancestor));
scanf("%d",&n);
for (int i=1;i<=n;i++)
father[i]=i;
for (int i=1;i<=n-1;i++)
{
int u,v;
scanf("%d%d",&u,&v);
flag[v]=true;
addedge(u,v);
addedge(v,u);
}
int a,b;
scanf("%d%d",&a,&b);
addquery(a,b,1);
addquery(b,a,1);
int root;
for (int i=1;i<=n;i++)
{ if (flag[i]==false)
{
root=i;
break;
}
}
lca(root);
printf("%d ",ans[1]);
}
int main()
{
scanf("%d",&t);
for (int i=1;i<=t;i++)
work();
return 0;
}