题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2586
最近公共祖先问题~~LAC离散算法
题目大意：一个村子里有n个房子，这n个房子用n-1条路连接起来，接下了有m次询问，每次询问两个房子a,b之间的距离是多少。
很明显的最近公共祖先问题，先建一棵树，然后求出每一点i到树根的距离dis[i],然后每次询问a，b之间的距离=dis[a]+dis[b]-2*dis[LCA(a,b)];
LCA(a,b)即是a，b的最近公共祖先。。
关于最近公共祖先，给大家推荐一个学长的博客http://www.cnblogs.com/ylfdrib/archive/2010/11/03/1867901.html，里面讲的很不错！！
# include<stdio.h>
# include<string.h>
# define N
# define M
struct node{
int from,to,next,val;
}edge[*N];
struct node1{
int from,to,next,num;
}edge1[*M];
int tol,head[N],head1[N],tol1,father[N],dis[N],LCA[M],n,m;
bool visit[N];
void add(int a,int b,int c)
{
edge[tol].from=a;edge[tol].to=b;edge[tol].next=head[a];edge[tol].val=c;head[a]=tol++;
}
void add1(int a,int b,int c)
{
edge1[tol1].from=a;edge1[tol1].to=b;edge1[tol1].next=head1[a];edge1[tol1].num=c;head1[a]=tol1++;
}
int find(int x)
{
if(x!=father[x])
father[x]=find(father[x]);
return father[x];
}
void tarjan(int u)
{
int j,v;
visit[u]=;
father[u]=u;
//////////////////
for(j=head1[u];j!=-;j=edge1[j].next)
{
v=edge1[j].to;
if(visit[v]) LCA[edge1[j].num]=find(v);
}
//////////////////
for(j=head[u];j!=-;j=edge[j].next)
{
v=edge[j].to;
if(!visit[v])
{
dis[v]=dis[u]+edge[j].val;
tarjan(v);
father[v]=u;
}
}
}
int main()
{
int i,ncase,a,b,c;
scanf("%d",&ncase);
while(ncase--)
{
scanf("%d%d",&n,&m);
tol=;
memset(head,-,sizeof(head));
for(i=;i<n;i++)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
memset(visit,,sizeof(visit));
tol1=;
memset(head1,-,sizeof(head1));
for(i=;i<=m;i++)
{
scanf("%d%d",&a,&b);
add1(a,b,i);
add1(b,a,i);
}
///LCA是一种离线算法，所以刚开始需要把所有的询问都输入，然后用邻接表进行存储，i表示第i次询问
dis[]=;
tarjan();
for(i=;i<tol1;i+=)
{
a=edge1[i].from;
b=edge1[i].to;
c=edge1[i].num;
printf("%d\n",dis[a]+dis[b]-*dis[LCA[c]]);
}
}
return ;
}
**************************
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std; const int NN=; int n,m;
vector<pair<int,int> > edge[NN],qe[NN];
vector<int> q1,q2; int p[NN];
int find(int x)
{
if (p[x]!=x) p[x]=find(p[x]);
return p[x];
} int sum=,ans[NN],dis[NN];
bool vis[NN]={};
void lca(int u,int fa)
{
p[u]=u;
for (int i=; i<edge[u].size(); i++)
{
int v=edge[u][i].first;
if (v==fa) continue;
dis[v]=dis[u]+edge[u][i].second;
lca(v,u);
p[v]=u;
}
vis[u]=true;
if (sum==m) return;
for (int i=; i<qe[u].size(); i++)
{
int v=qe[u][i].first;
if (vis[v])
ans[qe[u][i].second]=dis[u]+dis[v]-*dis[find(v)];
}
} int main()
{
int u,v,w; int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for (int i=; i<=n; i++)
{
edge[i].clear();
}
for (int i=; i<n; i++)
{
scanf("%d%d%d",&u,&v,&w);
edge[u].push_back(make_pair(v,w));
edge[v].push_back(make_pair(u,w));
} for (int i=; i<m; i++)
{
scanf("%d%d",&u,&v);
qe[u].push_back(make_pair(v,i));
qe[v].push_back(make_pair(u,i));
ans[i]=;
}
dis[]=;
lca(,);
for (int i=; i<m; i++) printf("%d\n",ans[i]);
}
return ;
}