WikiOI 2370スモールルームのツリー(最裸LCA)

2370小机房的树木时间限制:1 s空间限制:256000 KB题目等级:ダイヤモンドDiamond题解题题描述Description小机房有本煥狗种的树,树上有N个節点,節点符号为0到N-1,有2只虫叫飘狗和大吉狗,分居在两个不同的節点上.ある日、彼らは1つのノードに登ってベースを作りたいと思っていましたが、2匹の虫として、あまり精力を費やしたくありません.あるノードから父親ノードに登るにはcのエネルギーがかかることが知られています(父親ノードからこのノードに登るのも同じです).彼らは最も精力を費やした道を見つけて、基礎を作るときに精力を旺盛にしたいと思っています.彼らはあなたがこの道を見つけるためにプログラムを設計して、少なくともどれだけの精力を費やす必要があるかを教えてほしいと思っています.
Input Descriptionの最初の行を記述するnを入力し、次にn−1行の各行に3つの整数u,v,cを持つ.ノードuがノードvに登るのにcの労力がかかることを示す.n+1行目の整数mはm回のクエリを表す.次にm行の各行には2つの整数uがあり、vは2匹の虫がいるノード出力記述Output Descriptionにはm行があり、各行には整数があり、このクエリに対して得られた最短距離を表す.
サンプル入力Sample Input 3
1 0 1
2 0 1
3
1 0
2 0
1 2
サンプル出力Sample Output 1
1
2
データ範囲および提示Data Size&Hint 1<=n<=50000,1<=m<=75000,0<=c<=1000
LCAを学んだ後に書いた最初の練習問題は、裸だったが、基礎的で、後に書いたlcaの多くもこの問題のコードから進化した.

program mys;

type ab=^node;
node=record
data,ends:longint;
next:ab;
end;

var x,y,z,u,v,i,j,k,m,n:longint;
f,d,c:array[0..50000]of longint;
dp:array[0..50000,0..30] of longint;
b:array[0..50000]of boolean;
p,a,pa,pp:array[0..50000]of ab;

procedure add(x,y,z:longint);
var i:ab;
begin 
i:=p[x];
new(p[x]);
p[x]^.data:=z;
p[x]^.ends:=y;
p[x]^.next:=i;
end;

procedure dfs(x:longint);
var i:ab;
y:longint;
begin 
b[x]:=true;
i:=p[x];
while i<>nil do
begin 
if b[i^.ends]=false then 
begin 
f[i^.ends]:=x;
d[i^.ends]:=d[x]+1;
c[i^.ends]:=c[x]+i^.data;
dfs(i^.ends);
end;
i:=i^.next;
end;
b[x]:=false;
end;

function lca(u,v:longint):longint;
var i:longint;
begin
if d[u]then 
begin 
i:=u;
u:=v;
v:=i;
end;
i:=30;
while d[u]>d[v] do 
begin 
while d[dp[u,i]]do dec(i);
u:=dp[u,i];
end;
if u=v then exit(u);
i:=30;
while i>=0 do
begin 
while (i>=0) and(dp[u,i]=dp[v,i]) do dec(i);
if i>=0 then 
begin 
u:=dp[u,i];
v:=dp[v,i];
end;
end;
exit(f[u]);
end;

begin 
readln(n);
fillchar(f,sizeof(f),0);
for i:=1 to n do
f[i-1]:=i-1;
for i:=1 to n-1 do 
begin 
readln(u,v,z);
add(u,v,z);
add(v,u,z);
end;
dfs(0);
for i:=1 to n do 
dp[i-1,0]:=f[i-1];
for j:=1 to 30 do 
for i:=1 to n do 
dp[i-1,j]:=dp[dp[i-1,j-1],j-1];
readln(m);
for i:=1 to m do
begin  
readln(x,y);
z:=lca(x,y);
writeln(c[x]+c[y]-2*c[z]);
end;
end.