LCA问题有好几种做法，用到（tarjan）图拉算法的就有3种。具体可以看邝斌的博客。http://www.cnblogs.com/kuangbin/category/415390.html
几天的学习，我就弄懂了离线的Tarjan算法。在此，先鄙视一下哈工大出版的《图论及应用》，离线的Tarjan算法的模版用不了。害我白忙活。
poj1330的代码可以直接用来当模版。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=10010; int f[N], r[N], anc[N]; bool vis[N]; struct node { int to,next; }edge[N*2]; int head[N],tot; void addedge(int i, int j) { edge[tot].to=j;edge[tot].next=head[i];head[i]=tot++; edge[tot].to=i;edge[tot].next=head[j];head[j]=tot++; } struct NODE { int to,next,index;//index(查询编号) }query[N*2]; int h[N], res[N*2], tt, q; bool flag[N]; void add_q(int i, int j, int k) { query[tt].to=j;query[tt].next=h[i];query[tt].index=k;h[i]=tt++; query[tt].to=i;query[tt].next=h[j];query[tt].index=k;h[j]=tt++; } void init(int n) { for(int i=1;i<=n;i++) { f[i]=-1; r[i]=1; vis[i]=0; anc[i]=0; flag[i]=0; tot=tt=0; } memset(head,-1,sizeof(head)); memset(h,-1,sizeof(h)); } int Find(int x) { if(-1==f[x]) return x; return f[x]=Find(f[x]); } void Link(int x,int y) { int a=Find(x),b=Find(y); if(a!=b) { if(r[a]<=r[b]) {f[a]=b; r[b]+=r[a];} else {f[b]=a; r[a]+=r[b];} } } void LCA(int u) { anc[u]=u; vis[u]=1; for(int k=head[u];k!=-1;k=edge[k].next) { int v=edge[k].to; if(vis[v]) continue; LCA(v); Link(u,v); anc[Find(u)]=u; } for(int k=h[u];k!=-1;k=query[k].next) { int v=query[k].to; if(vis[v]) { res[query[k].index]=anc[Find(v)]; } } } int main() { //freopen("test.txt","r",stdin); int T,n,u,v,i; scanf("%d",&T); while(T--) { scanf("%d",&n); init(n); for(i=1;i<n;i++) { scanf("%d%d",&u,&v); flag[v]=1; addedge(u,v); } q=1; for(i=0;i<q;i++) { scanf("%d%d",&u,&v); add_q(u,v,i); } int root; for(i=1;i<=n;i++) if(!flag[i]) {root=i; break;} LCA(root); for(i=0;i<q;i++) printf("%d ",res[i]); } return 0; }
hdu2586的要求有些提高，还要求距离。假如要求u和v两点的距离，可以通过求u和v到根结点的距离,还有他们的LCA到根节点的距离。公式是dis[u] + dis[v] -2*dis[LCA[u,v]]。
//hdu2586 O(n+q) #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=40010; int f[N], r[N], anc[N]; bool vis[N]; struct node { int to,next,w; }edge[N*2]; int head[N],tot; void addedge(int i, int j,int w) { edge[tot].to=j;edge[tot].w=w;edge[tot].next=head[i];head[i]=tot++; edge[tot].to=i;edge[tot].w=w;edge[tot].next=head[j];head[j]=tot++; } struct NODE { int to,next,index;//index(查询编号) }query[N*2]; int h[N], res[N*2], tt, q, dist[N]; bool flag[N]; void add_q(int i, int j, int k) { query[tt].to=j;query[tt].next=h[i];query[tt].index=k;h[i]=tt++; query[tt].to=i;query[tt].next=h[j];query[tt].index=k;h[j]=tt++; } void init(int n) { for(int i=1;i<=n;i++) { f[i]=-1; r[i]=1; vis[i]=0; anc[i]=0; flag[i]=0; tot=tt=0; } memset(head,-1,sizeof(head)); memset(h,-1,sizeof(h)); } int Find(int x) { if(-1==f[x]) return x; return f[x]=Find(f[x]); } void Link(int x,int y) { int a=Find(x),b=Find(y); if(a!=b) { if(r[a]<=r[b]) {f[a]=b; r[b]+=r[a];} else {f[b]=a; r[a]+=r[b];} } } void LCA(int u) { anc[u]=u; vis[u]=1; for(int k=head[u];k!=-1;k=edge[k].next) { int v=edge[k].to; if(vis[v]) continue; dist[v]=dist[u]+edge[k].w; LCA(v); Link(u,v); anc[Find(u)]=u; } for(int k=h[u];k!=-1;k=query[k].next) { int v=query[k].to; if(vis[v]) res[query[k].index]=anc[Find(v)]; } } int a[N],b[N]; int main() { //freopen("test.txt","r",stdin); int T,n,u,v,i,m,w; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&q); init(n); for(i=1;i<n;i++) { scanf("%d%d%d",&u,&v,&w); flag[v]=1; addedge(u,v,w); } for(i=0;i<q;i++) { scanf("%d%d",&u,&v); a[i]=u;b[i]=v; add_q(u,v,i); } int root; for(i=1;i<=n;i++) if(!flag[i]) {root=i; break;} dist[root]=0; LCA(root); for(i=0;i<q;i++) printf("%d ",dist[a[i]]+dist[b[i]]-2*dist[res[i]]); } return 0; }