Codevs P1036 商务旅行

2024-03-15 09:40

文章标签 codevs p1036 商务旅行

本文主要是介绍Codevs P1036 商务旅行，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Codevs P1036 商务旅行

题目描述 Description

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

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

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

输入描述 Input Description

输入文件中的第一行有一个整数N，1<=n<=30 000，为城镇的数目。下面N-1行，每行由两个整数a 和b (1<=a, b<=n; a<>b)组成，表示城镇a和城镇b有公路连接。在第N+1行为一个整数M，下面的M行，每行有该商人需要顺次经过的各城镇编号。

输出描述 Output Description

在输出文件中输出该商人旅行的最短时间。

样例输入 Sample Input

5
1 2
1 5
3 5
4 5
4
1
3
2
5

样例输出 Sample Output

分析

该题要去寻找最短路径那么就是其到最近公共祖先的距离和。
由此衍生出两种做法
第一种用各自到根的距离减去二倍最近公共祖先到根的距离
第二种则是距离也采用倍增的思想；（详见代码）

代码如下

program p1036;
type point=^rec;rec=recorde:longint;s:point;end;
var ans,head,rear,s,e,n,m,i,j,k:longint;vertex:array[1..30000] of point;father,g:array[0..30000,0..20] of int64;depth:array[0..30000] of int64;can:array[1..30000] of boolean;
procedure insert(s,e:longint);
var p:point;
beginnew(p);p^.e:=e;p^.s:=vertex[s];vertex[s]:=p;
end;
procedure dfs(head,step:longint;p:point);
begincan[head]:=false;while p<>nil dobeginif can[p^.e]thenbegincan[p^.e]:=false;father[p^.e,0]:=head;depth[p^.e]:=step;g[p^.e,0]:=1;dfs(p^.e,step+1,vertex[p^.e]);end;p:=p^.s;end;
end;procedure lca(l,r:longint);
var j:longint;
beginfor j:=20 downto 0 dobeginif depth[father[l,j]]>=depth[r]thenbeginans:=ans+g[l,j];l:=father[l,j];end;end;if l=r then exit;for j:=20 downto 0 dobeginif father[l,j]<>father[r,j]thenbeginans:=ans+g[l,j]+g[r,j];l:=father[l,j];r:=father[r,j];end;end;ans:=ans+g[l,0]+g[r,0];exit;
end;beginreadln(n);for i:=1 to n-1 dobeginreadln(s,e);insert(s,e);insert(e,s);end;for i:=1 to n do can[i]:=true;readln(m);dfs(1,1,vertex[1]);father[1,0]:=1;g[1,0]:=0;for j:=1 to 20 dofor i:=1 to n dobeginfather[i,j]:=father[father[i,j-1],j-1];g[i,j]:=g[i,j-1]+g[father[i,j-1],j-1];end;ans:=0;head:=1;for i:=1 to m dobeginreadln(rear);if depth[rear]>depth[head]then lca(rear,head)else lca(head,rear);head:=rear;end;write(ans);
end.