链接：http://acm.hdu.edu.cn/showproblem.php?pid=2586
【题意】
给出一个N 个和N-1条边的连通图，询问任意两点间的距离。N<=40000 。
【分析】
点太多了，用最短路算法来求超时。只够求一个点的单源最短路，而且不能用O(n2)的算法。正确的做法就是求出两点的最近公共祖先，利用点v到树的根节点距离dis[v]来换算。设要求的两点分别为u和v, 那么u和v的距离d=dis[u]+dis[v]-2*dis[LCA(u,v)] 。
现在还有一个问题就是输入是一个图，并不是一棵树，怎么有根节点？怎么确定父子关系？
这个挺好办的，随便选一个点当根节点，从这个节点开始分层遍历，这样就有树的结构了。求dis数组我原先是用单源最短路来求的，不过仔细想下，因为原图就是一棵树，从根节点到任意点的路径是唯一的，于是就可以用递推的方式求的，在分层遍历中计算就好了。遍历递归的层数有点多，可能会爆栈。
这里我使用LCA转RMQ的方法来求的。
【代码】
#pragma comment(linker, "/STACK:1024000000,1024000000") //扩栈
#include <stdio.h>
#include <string.h>
#include <vector>
#include <cmath>
using namespace std;
int n,m;
struct edge
{
int d,v,next;
edge(){}
edge(int _d,int _v,int _next)
{
d=_d;v=_v;next=_next;
}
}data[];
int map[];
int pool;
void addedge(int s,int e,int v)
{
int t=map[s];
data[pool++]=edge(e,v,t);
map[s]=pool-;
}
vector<int> f;
vector<int> b;
bool ifv[];
int pos[];
int dis[];
void dfs(int cur,int c)
{
if (cur< || cur>=n) return;
ifv[cur]=true;
pos[cur]=(int)f.size();
f.push_back(cur);
b.push_back(c);
int p=map[cur];
while (p!=-)
{
if (!ifv[data[p].d])
{
dis[data[p].d]=dis[cur]+data[p].v;
dfs(data[p].d,c+);
f.push_back(cur);
b.push_back(c);
}
p=data[p].next;
}
}
int rmq[][];
void makermq(int n,int bitn)
{
for (int i=; i<n; ++i)
rmq[i][]=b[i];
for (int j=; j<bitn; ++j)
for (int i=; i<n; ++i)
{
if (i+(<<(j-))>=n) break;
rmq[i][j]=min(rmq[i][j-],rmq[i+(<<(j-))][j-]);
}
}
int query(int s,int e)
{
int k=(int)((log(e-s+1.0)/log(2.0)));
return min(rmq[s][k],rmq[e-(<<k)+][k]);
}
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
pool=;
f.clear();
b.clear();
memset(map,-,sizeof map);
memset(ifv,,sizeof ifv);
scanf("%d%d",&n,&m);
int s,e,v;
for (int i=;i<n-;++i)
{
scanf("%d%d%d",&s,&e,&v);
addedge(s-,e-,v);
addedge(e-,s-,v);
}
dis[]=;
dfs(,);
makermq(b.size(),(int)(log((double)b.size())/log(2.0)));
for (int i=;i<m;++i)
{
int u,v;
scanf("%d%d",&u,&v);
--u;--v;
int s=pos[u];
int e=pos[v];
if (s>e) swap(s,e);
int k=query(s,e);
k=f[k];
int ans=dis[u]+dis[v]-*dis[k];
printf("%d\n",ans);
}
}
}