2 3 2 1 2 10 3 1 15 1 2 2 3 2 2 1 2 100 1 2 2 1
10 25 100 100
好久没写lca，回顾一下。
代码：
/* ***********************************************
Author :rabbit
Created Time :2014/3/29 11:40:24
File Name :E.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=50010;
int head[maxn],tol,dis[maxn],fa[maxn][20],dep[maxn];
struct node{
int next,to,val;
}edge[5*maxn];
void addedge(int u,int v,int w){
edge[tol].to=v;
edge[tol].next=head[u];
edge[tol].val=w;
head[u]=tol++;
}
void bfs(int root){
queue<int> q;
fa[root][0]=root;dep[root]=0;dis[root]=0;
q.push(root);
while(!q.empty()){
int u=q.front();q.pop();
for(int i=1;i<20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;if(v==fa[u][0])continue;
dep[v]=dep[u]+1;dis[v]=dis[u]+edge[i].val;fa[v][0]=u;
q.push(v);
}
}
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=0;i<20;i++)if((dep[x]-dep[y])&(1<<i))x=fa[x][i];
if(x==y)return x;
for(int i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
int T,n,m;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
memset(head,-1,sizeof(head));tol=0;
for(int i=1;i<n;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
bfs(1);
while(m--){
int u,v;
scanf("%d%d",&u,&v);
printf("%d\n",dis[u]+dis[v]-2*dis[lca(u,v)]);
}
}
return 0;
}
hdu 2586 lca模板题,布布扣,bubuko.com
原文：http://blog.csdn.net/xianxingwuguan1/article/details/22483633