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)而已)
1 type
2 point=^node;
3 node=record
4 g,w:longint;
5 next:point;
6 end;
7
8 var
9 i,j,k,l,m,n:longint;
10 a,b:array[0..15,0..15000] of longint;
11 c:array[0..15000] of point;
12 d:array[0..15000] of longint;
13 procedure swap(var x,y:longint);
14 var z:longint;
15 begin
16 z:=x;x:=y;y:=z;
17 end;
18 procedure add(x,y,z:longint);
19 var
20 p:point;
21 begin
22 new(p);
23 p^.w:=z;
24 p^.g:=y;
25 p^.next:=c[x];
26 c[x]:=p;
27 end;
28 procedure dfs(x:longint);
29 var
30 p:point;
31 begin
32 p:=c[x];
33 while p<>nil do
34 begin
35 if d[p^.g]=0 then
36 begin
37 d[p^.g]:=d[x]+1;
38 a[0,p^.g]:=x;
39 b[0,p^.g]:=p^.w;
40 dfs(p^.g);
41 end;
42 p:=p^.next;
43 end;
44 end;
45 function getfat(x,y:longint):longint;
46 var i:longint;
47 begin
48 i:=0;
49 while y>0 do
50 begin
51 if odd(y) then x:=a[i,x];
52 inc(i);
53 y:=y div 2;
54 end;
55 exit(x);
56 end;
57 function getcom(x,y:longint):longint;
58 var i,j:longint;
59 begin
60 if d[x]<d[y] then swap(x,y);
61 x:=getfat(x,d[x]-d[y]);
62 if x=y then exit(x);
63 i:=15;
64 while i>=0 do
65 begin
66 if a[i,x]<>a[i,y] then
67 begin
68 x:=a[i,x];
69 y:=a[i,y];
70 end;
71 dec(i);
72 end;
73 exit(a[0,x]);
74 end;
75 function getsum(x,y:longint):longint;
76 var i,j,k:longint;
77 begin
78 i:=0;j:=0;
79 while y>0 do
80 begin
81 if odd(y) then
82 begin
83 j:=j+b[i,x];
84 x:=a[i,x];
85 end;
86 y:=y div 2;
87 inc(i);
88 end;
89 exit(j);
90 end;
91 begin
92 readln(n,m);
93 for i:=1 to n do c[i]:=nil;
94 for i:=1 to n-1 do
95 begin
96 readln(j,k,l);
97 add(j,k,l);
98 add(k,j,l);
99 end;
100 fillchar(d,sizeof(d),0);
101 d[1]:=1;
102 dfs(1);
103
104 for i:=1 to 15 do
105 for j:=1 to n do
106 a[i,j]:=a[i-1,a[i-1,j]];
107
108 for i:=1 to 15 do
109 for j:=1 to n do
110 b[i,j]:=b[i-1,j]+b[i-1,a[i-1,j]];
111
112 for i:=1 to m do
113 begin
114 readln(j,k);
115 l:=getcom(j,k);
116 writeln(getsum(j,d[j]-d[l])+getsum(k,d[k]-d[l]));
117 end;
118 end.