小机房有棵焕狗种的树，树上有N个节点，节点标号为0到N-1，有两只虫子名叫飘狗和大吉狗，分居在两个不同的节点上。有一天，他们想爬到一个节点上去搞基，但是作为两只虫子，他们不想花费太多精力。已知从某个节点爬到其父亲节点要花费 c 的能量（从父亲节点爬到此节点也相同），他们想找出一条花费精力最短的路，以使得搞基的时候精力旺盛，他们找到你要你设计一个程序来找到这条路，要求你告诉他们最少需要花费多少精力。//题面有点恶心，但题还是挺不错的233
第一行一个n，接下来n-1行每一行有三个整数u，v, c 。表示节点 u 爬到节点 v 需要花费 c 的精力。
第n+1行有一个整数m表示有m次询问。接下来m行每一行有两个整数 u ，v 表示两只虫子所在的节点
一共有m行，每一行一个整数，表示对于该次询问所得出的最短距离。
3
1 0 1
2 0 1
3
1 0
2 0
1 2
1
1
2
1<=n<=50000， 1<=m<=75000， 0<=c<=1000
LCA，最近公共祖先。
用一个p数组储存节点i到根节点的距离。假设要求节点x与y之间的距离，则答案为p[x]+p[y]-2*p[lca(x,y)]。
代码：
1 var p,f,ne,c,b,d:array[0..200010] of longint;
2 var fa:array[0..100010,0..30] of longint;
3 var n,m,i,j,k,z,x,y:longint;
4 var v:array[0..100010] of boolean;
5 procedure add(x,y,z:longint);//建邻接表
6 begin
7 inc(m);c[m]:=z;b[m]:=y;ne[m]:=f[x];f[x]:=m;
8 end;
9 function log(x:longint):longint;//求log
10 begin
11 exit(trunc(ln(x)/ln(2)));
12 end;
13 procedure dfs(dep,num:longint);
14 var j:longint;
15 begin
16 j:=f[num];
17 v[num]:=true;//记录过则标记
18 d[num]:=dep;//记录深度
19 while j>0 do
20 begin
21 if not v[b[j]] then//没记录过的
22 begin
23 p[b[j]]:=p[num]+c[j];//更新距离
24 dfs(dep+1,b[j]);fa[b[j],0]:=num;//fa[i,j]指i的2^j倍祖先
25 end;
26 j:=ne[j];
27 end;
28 end;
29 function lca(x,y:longint):longint;
30 var t,i,j,k:longint;
31 begin
32 if d[x]<d[y] then
33 begin
34 t:=x;x:=y;y:=t;//保证d[x]≥d[y]
35 end;
36 for i:=k downto 0 do if d[x]-1<<i>=d[y] then x:=fa[x,i];//x向上调,直至两点在同一深度
37 if x=y then exit(x);//同一点则返回x
38 for i:=k downto 0 do//爬树法
39 begin
40 if fa[x,i]<>fa[y,i] then//同时向上调
41 begin
42 x:=fa[x,i];y:=fa[y,i];
43 end;
44 end;
45 exit(fa[x,0]);//返回其中一个点的父亲节点
46 end;
47 begin
48 readln(n);
49 fillchar(f,sizeof(f),255);//f数组设为-1
50 for i:=1 to n-1 do
51 begin
52 readln(x,y,z);
53 add(x,y,z);add(y,x,z);//建邻接表
54 end;
55 dfs(1,0);//预处理d(深度),p(与根节点距离)数组
56 k:=log(n);
57 for i:=1 to k do
58 for j:=1 to n do fa[j,i]:=fa[fa[j,i-1],i-1];
59 readln(m);
60 for i:=1 to m do
61 begin
62 readln(x,y);
63 writeln(p[x]+p[y]-p[lca(x,y)]*2);
64 end;
65 end.
欢迎转载，请注明出处。
原文：http://www.cnblogs.com/HAdolf-HQY/p/6389609.html