题意：
某村庄有n个小屋，n-1条道路连接着n个小屋（无环），求村庄A到村庄B的距离，要求是经过任一村庄不超过一次。
题解：
求出 lca = LCA(u,v) ， 然后答案便是dist[u] + dist[v] - 2 * dist[lca];
AC代码：
#include<iostream>
#include<vector>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define pb(x) push_back(x)
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn=4e4+; int n,q;
int dist[maxn];//dist[i]: 节点i与节点1的距离，假定1为根节点
int vs[*maxn];//欧拉序列
int depth[*maxn];//深度序列
int pos[maxn];//pos[i]:节点i在欧拉序列中第一次出现的位置
bool vis[maxn];
struct Edge
{
int to;
int w;
Edge(int a=,int b=):to(a),w(b){}
};
vector<Edge >G[maxn];
void addEdge(int u,int v,int w)
{
G[u].pb(Edge(v,w));
}
struct RMQ
{
int dp[][*maxn];
void rmq()
{
int tot=*n-;
for(int i=;i <= tot;++i)
dp[][i]=i;
for(int k=;(<<k) <= tot;++k)
for(int i=;((<<k)+i-) <= tot;++i)
if(depth[dp[k-][i]] > depth[dp[k-][i+(<<(k-))]])
dp[k][i]=dp[k-][i+(<<(k-))];
else
dp[k][i]=dp[k-][i];
}
int lca(int u,int v)
{
u=pos[u],v=pos[v];
if(u > v)
swap(u,v);
int k=log(v-u+)/log();
return vs[min(dp[k][u],dp[k][v-(<<k)+])];
}
}_rmq;
void Dfs(int u,int dis,int dep,int &k)
{
vs[++k]=u;
depth[k]=dep;
pos[u]=k;
dist[u]=dis;
vis[u]=true;
for(int i=;i < G[u].size();++i)
{
int to=G[u][i].to;
int w=G[u][i].w;
if(!vis[to])
{
Dfs(to,dis+w,dep+,k);
vs[++k]=u;
depth[k]=dep;
}
}
}
void LCA()
{
int k=;
Dfs(,,,k);
_rmq.rmq();
}
void Init()
{
mem(vis,false);
for(int i=;i <= n;++i)
G[i].clear();
}
int main()
{
// freopen("C:/Users/hyacinthLJP/Desktop/stdin/hdu2586.txt","r",stdin);
int t;
scanf("%d",&t);
while(t--)
{
Init();
scanf("%d%d",&n,&q);
for(int i=;i < n;++i)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addEdge(u,v,w);
addEdge(v,u,w);
}
LCA();
for(int i=;i <= q;++i)
{
int u,v;
scanf("%d%d",&u,&v);
int lca=_rmq.lca(u,v);
printf("%d\n",dist[u]+dist[v]-*dist[lca]);
}
}
return ;
}
基于RMQ的LCA