2953: [Poi2002]商务旅行
2953: [Poi2002]商务旅行
HansBug
发布于 2018-04-10 16:42:54
发布于 2018-04-10 16:42:54
2953: [Poi2002]商务旅行
Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 8 Solved: 8
Description
某首都城市的商人要经常到各城镇去做生意，他们按自己的路线去做，目的是为了更好的节约时间。
假设有N个城镇，首都编号为1，商人从首都出发，其他各城镇之间都有道路连接，任意两个城镇之间如果有直连道路，在他们之间行驶需要花费单位时间。该国公路网络发达，从首都出发能到达任意一个城镇，并且公路网络不会存在环。
你的任务是帮助该商人计算一下他的最短旅行时间。
Input
第一行有一个整数N，1<=n<=30 000，为城镇的数目。下面N-1行，每行由两个整数a 和b (1<=a, b<=n; a<>b)组成，表示城镇a和城镇b有公路连接。在第N+1行为一个整数M，下面的M行，每行有该商人需要顺次经过的各城镇编号。
Output
输出该商人旅行的最短时间。
Sample Input
5 1 2 1 5 3 5 4 5 4 1 3 2 5
Sample Output
7
HINT
Source
题解：本来想在codevs做一道线段树题目的，可是进入线段树分类后就发现了这个（HansBug：呵呵呵呵这个也叫线段树我也是醉了）只要学过LCA的童鞋不难发现这就是一个最裸的LCA，直接上倍增搞搞就行了，连加上边长数组都免了。。。
1 type
2 point=^node;
3 node=record
4 g:longint;
5 next:point;
6 end;
7
8 var
9 i,j,k,l,m,n,t:longint;
10 a:array[0..50000] of point;
11 c:array[0..20,0..50000] of longint;
12 d:array[0..50000] of longint;
13 function min(x,y:longint):longint;inline;
14 begin
15 if x<y then min:=x else min:=y;
16 end;
17 function max(x,y:longint):longint;inline;
18 begin
19 if x>y then max:=x else max:=y;
20 end;
21 procedure swap(var x,y:longint);inline;
22 var z:longint;
23 begin
24 z:=x;x:=y;y:=z;
25 end;
26 procedure add(x,y:longint);inline;
27 var p:point;
28 begin
29 new(p);
30 p^.g:=y;
31 p^.next:=a[x];
32 a[x]:=p;
33 end;
34 procedure dfs(x:longint);inline;
35 var p:point;
36 begin
37 p:=a[x];
38 while p<>nil do
39 begin
40 if c[0,p^.g]=0 then
41 begin
42 c[0,p^.g]:=x;
43 d[p^.g]:=d[x]+1;
44 dfs(p^.g);
45 end;
46 p:=p^.next;
47 end;
48 end;
49 function getfat(x,y:longint):longint;inline;
50 var i,j,k:longint;
51 begin
52 i:=0;
53 while y>0 do
54 begin
55 if odd(y) then x:=c[i,x];
56 inc(i);y:=y div 2;
57 end;
58 getfat:=x;
59 end;
60 function dis(x,y:longint):longint;
61 var
62 a1,a2,a3,i,j,k,l:longint;
63 begin
64 if d[x]<d[y] then swap(x,y);
65 a1:=x;a2:=y;
66 x:=getfat(x,d[x]-d[y]);
67 if x=y then exit(d[a1]-d[a2]);
68 for i:=20 downto 0 do
69 begin
70 if c[i,x]=0 then continue;
71 if c[i,x]<>c[i,y] then
72 begin
73 x:=c[i,x];
74 y:=c[i,y];
75 end
76 end;
77 a3:=c[0,x];
78 exit(d[a1]+d[a2]-d[a3]-d[a3]);
79 end;
80
81 begin
82 readln(n);
83 for i:=1 to n do a[i]:=nil;
84 for i:=1 to n-1 do
85 begin
86 readln(j,k);
87 add(j,k);add(k,j);
88 end;
89 fillchar(c,sizeof(c),0);
90 fillchar(d,sizeof(d),0);
91 c[0,1]:=-1;
92 dfs(1);c[0,1]:=0;
93 for i:=1 to 20 do
94 for j:=1 to n do
95 c[i,j]:=c[i-1,c[i-1,j]];
96 readln(m);
97 readln(j);l:=0;
98 for i:=1 to m-1 do
99 begin
100 k:=j;
101 readln(j);
102 t:=dis(k,j);
103 l:=l+t;
104 end;
105 writeln(l);
106 readln;
107 end.
108 本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-01-18 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录