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 条评论
登录 后参与评论

相关文章

来自专栏Java学习网

Java细粒度锁实现的3种方式

Java细粒度锁实现的3种方式 最近在工作上碰见了一些高并发的场景需要加锁来保证业务逻辑的正确性,并且要求加锁后性能不能受到太大的影响。初步的想法是通过数据的时...

44590
来自专栏司想君

前端也要学系列:设计模式之装饰者模式

今天我们来讲另外一个非常实用的设计模式:装饰者模式。这个名字听上去有些莫名其妙,不着急,我们先来记住它的一个别名:包装器模式。

9920
来自专栏小二的折腾日记

LeetCode-32-Longest-Valid-Parentheses

表示这是一道没有看懂题目的题,看到题目的难度是hard,但是自己的想法很简答,以为直接一个栈就可以了。。 too young啊

12330
来自专栏java工会

一分钟搞明白java8中的lambda|文末红包

23750
来自专栏软件开发

一种绝对提高开发水平的方法

如果做了多年开发的你发现自己的水平一直上不去,你可能要提高自己的英文水平了,英语就是你技术的瓶颈,对有些人可能是硬伤。

43240
来自专栏Android群英传

我与 Kotlin 的爱恨情仇之浅谈 block

14040
来自专栏喔家ArchiSelf

一行Python代码

自从08年接触Python,就有爱不释手的感觉,逐渐地,有些不忍地疏远了Perl 和Shell编程,因为python 的优雅么? 不全是,主要是可以高效开发吧。

28940
来自专栏一个会写诗的程序员的博客

快速开始 Hello World 和 Python 之禅环境安装Python IDE Shell 界面

优美胜于丑陋(Python 以编写优美的代码为目标) 明了胜于晦涩(优美的代码应当是明了的,命名规范,风格相似) 简洁胜于复杂(优美的代码应当是简洁的,不要...

9030
来自专栏数据结构与算法

畅通工程

•Problem Description •某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何...

36160
来自专栏烙馅饼喽的技术分享

记一个脚本解释器的开发

最近可以有1个月左右的空闲,可以稍微整理一下这个脚本解释器的开发过程。 一、缘由   2014年左右,我们使用AIR技术,开发了一个3D战争类型的手游。那时候手...

45270

扫码关注云+社区

领取腾讯云代金券