专栏首页HansBug's Lab2953: [Poi2002]商务旅行

2953: [Poi2002]商务旅行

2953: [Poi2002]商务旅行

Time Limit: 3 Sec  Memory Limit: 128 MB

Submit: 8  Solved: 8

[Submit][Status]

Description

某首都城市的商人要经常到各城镇去做生意,他们按自己的路线去做,目的是为了更好的节约时间。

假设有N个城镇,首都编号为1,商人从首都出发,其他各城镇之间都有道路连接,任意两个城镇之间如果有直连道路,在他们之间行驶需要花费单位时间。该国公路网络发达,从首都出发能到达任意一个城镇,并且公路网络不会存在环。

你的任务是帮助该商人计算一下他的最短旅行时间。

Input

第一行有一个整数N,1<=n<=30 000,为城镇的数目。下面N-1行,每行由两个整数a 和b (1<=ab<=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            

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法模板——LCA(最近公共祖先)

    实现的功能如下——在一个N个点的无环图中,共有N-1条边,M个访问中每次询问两个点的距离 原理——既然N个点,N-1条边,则说明这是一棵树,而且联通。所以以1为...

    HansBug
  • 3732: Network

    3732: Network Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 395  Solved: 179 ...

    HansBug
  • 1935: [Shoi2007]Tree 园丁的烦恼

    1935: [Shoi2007]Tree 园丁的烦恼 Time Limit: 15 Sec  Memory Limit: 357 MB Submit: 648 ...

    HansBug
  • 3732: Network

    3732: Network Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 395  Solved: 179 ...

    HansBug
  • 算法模板——LCA(最近公共祖先)

    实现的功能如下——在一个N个点的无环图中,共有N-1条边,M个访问中每次询问两个点的距离 原理——既然N个点,N-1条边,则说明这是一棵树,而且联通。所以以1为...

    HansBug
  • 算法模板——线段树7(骰子翻转问题)

    实现功能:首先输入一个长度为N的序列,由1-4组成(1表示向前滚一下,2表示向后滚一下,3表示向左滚一下,4表示向右滚一下,骰子原始状态:上1前2左4右5后3下...

    HansBug
  • Codevs2776 寻找代表元

    2776 寻找代表元  时间限制: 1 s  空间限制: 256000 KB  题目等级 : 黄金 Gold 题目描述 Description 广州二中苏元实...

    HansBug
  • 算法模板——二分图匹配

    实现功能为二分图匹配 原理:匈牙利算法,核心思想——匹配上了就配,没直接匹配上也要通过前面的腾出位置让这个匹配上(详见:趣写算法系列之——匈牙利算法) 本程序以...

    HansBug
  • 3386/1752: [Usaco2004 Nov]Til the Cows Come Home 带奶牛回家

    3386/1752: [Usaco2004 Nov]Til the Cows Come Home 带奶牛回家 Time Limit: 1 Sec  Memory...

    HansBug
  • 算法模板——Dinic最小费用最大流

    实现功能:输入M,N,S,T;接下来M行输入M条弧的信息(包括起点,终点,流量,单位费用);实现功能是求出以S为源点,T为汇点的网络最大流的最小费用 其实相当的...

    HansBug

扫码关注云+社区

领取腾讯云代金券