# 2953: [Poi2002]商务旅行

## 2953: [Poi2002]商务旅行

Time Limit: 3 Sec  Memory Limit: 128 MB

Submit: 8  Solved: 8

[Submit][Status]

## Sample Input

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

7

## 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为...

• ### 3732: Network

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

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

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

• ### 3732: Network

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

• ### 算法模板——LCA（最近公共祖先）

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

• ### 算法模板——线段树7（骰子翻转问题）

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

• ### Codevs2776 寻找代表元

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

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

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

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

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

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

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