1602: [Usaco2008 Oct]牧场行走
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1211 Solved: 616
[Submit][Status]
Description
N头牛（2<=n<=1000）别人被标记为1到n，在同样被标记1到n的n块土地上吃草，第i头牛在第i块牧场吃草。 这n块土地被n-1条边连接。 奶牛可以在边上行走，第i条边连接第Ai，Bi块牧场，第i条边的长度是Li（1<=Li<=10000）。 这些边被安排成任意两头奶牛都可以通过这些边到达的情况，所以说这是一棵树。 这些奶牛是非常喜欢交际的，经常会去互相访问,他们想让你去帮助他们计算Q(1<=q<=1000)对奶牛之间的距离。
Input
*第一行：两个被空格隔开的整数：N和Q
*第二行到第n行：第i+1行有两个被空格隔开的整数：AI，BI，LI
*第n+1行到n+Q行：每一行有两个空格隔开的整数：P1，P2，表示两头奶牛的编号。
Output
*第1行到第Q行：每行输出一个数，表示那两头奶牛之间的距离。
Sample Input
4 2
2 1 2
4 3 2
1 4 3
1 2
3 2
Sample Output
2
7
HINT
Source
题解：这是一个还算比较裸的LCA（最近公公祖先问题），我用的是倍增算法（初始化O(nlogn)，每次查询O(nlogn)）然后只要用一个DFS建树，然后A之（以前一直以为DFS建树绝对会爆掉，但仔细一想DFS复杂度只要用邻接表存储最初的图的话，不过才O(2n)而已）
type
point=^node;
node=record
g,w:longint;
next:point;
end; var
i,j,k,l,m,n:longint;
a,b:array[..,..] of longint;
c:array[..] of point;
d:array[..] of longint;
procedure swap(var x,y:longint);
var z:longint;
begin
z:=x;x:=y;y:=z;
end;
procedure add(x,y,z:longint);
var
p:point;
begin
new(p);
p^.w:=z;
p^.g:=y;
p^.next:=c[x];
c[x]:=p;
end;
procedure dfs(x:longint);
var
p:point;
begin
p:=c[x];
while p<>nil do
begin
if d[p^.g]= then
begin
d[p^.g]:=d[x]+;
a[,p^.g]:=x;
b[,p^.g]:=p^.w;
dfs(p^.g);
end;
p:=p^.next;
end;
end;
function getfat(x,y:longint):longint;
var i:longint;
begin
i:=;
while y> do
begin
if odd(y) then x:=a[i,x];
inc(i);
y:=y div ;
end;
exit(x);
end;
function getcom(x,y:longint):longint;
var i,j:longint;
begin
if d[x]<d[y] then swap(x,y);
x:=getfat(x,d[x]-d[y]);
if x=y then exit(x);
i:=;
while i>= do
begin
if a[i,x]<>a[i,y] then
begin
x:=a[i,x];
y:=a[i,y];
end;
dec(i);
end;
exit(a[,x]);
end;
function getsum(x,y:longint):longint;
var i,j,k:longint;
begin
i:=;j:=;
while y> do
begin
if odd(y) then
begin
j:=j+b[i,x];
x:=a[i,x];
end;
y:=y div ;
inc(i);
end;
exit(j);
end;
begin
readln(n,m);
for i:= to n do c[i]:=nil;
for i:= to n- do
begin
readln(j,k,l);
add(j,k,l);
add(k,j,l);
end;
fillchar(d,sizeof(d),);
d[]:=;
dfs(); for i:= to do
for j:= to n do
a[i,j]:=a[i-,a[i-,j]]; for i:= to do
for j:= to n do
b[i,j]:=b[i-,j]+b[i-,a[i-,j]]; for i:= to m do
begin
readln(j,k);
l:=getcom(j,k);
writeln(getsum(j,d[j]-d[l])+getsum(k,d[k]-d[l]));
end;
end.