# 3732: Network

## 3732: Network

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 395  Solved: 179

[Submit][Status]

## Output

对每个询问，输出最长的边最小值是多少。

## Sample Input

6 6 8 1 2 5 2 3 4 3 4 3 1 4 8 2 5 7 4 6 2 1 2 1 3 1 4 2 3 2 4 5 1 6 2 6 1

5 5 5 4 4 7 4 5

## HINT

1 <= N <= 15,000  1 <= M <= 30,000  1 <= d_j <= 1,000,000,000  1 <= K <= 15,000

## Source

```  1 type
2     point=^node;
3     node=record
4                w,g:longint;
5                next:point;
6     end;
7
8 var
9    i,j,k,l,m,n,t:longint;
10    a:array[0..40000] of point;
11    b:array[0..40000,1..3] of longint;
12    c,f,g,h:array[0..40000] of longint;
13    d:array[0..20,0..40000] of longint;
14    e:array[0..20,0..40000] of longint;
15 function getfat(x:longint):longint;inline;
16          begin
17               while x<>c[x] do x:=c[x];
18               getfat:=x;
19          end;
20 function tog(x,y:longint):boolean;inline;
21          begin
22               exit(getfat(x)=getfat(y));
23          end;
24 procedure merge(x,y:longint);inline;
25           begin
26                c[getfat(x)]:=getfat(y);
27           end;
28
30           var p:point;
31           begin
32                new(p);
33                p^.g:=y;
34                p^.w:=z;
35                p^.next:=a[x];
36                a[x]:=p;
37           end;
38 procedure swap(var x,y:longint);inline;
39           var z:longint;
40           begin
41                z:=x;x:=y;y:=z;
42           end;
43 procedure sort(l,r:longint);inline;
44           var i,j,x,y:longint;
45           begin
46                i:=l;j:=r;x:=b[(l+r) div 2,3];
47                repeat
48                      while b[i,3]<x do inc(i);
49                      while b[j,3]>x do dec(j);
50                      if i<=j then
51                         begin
52                              swap(b[i,1],b[j,1]);
53                              swap(b[i,2],b[j,2]);
54                              swap(b[i,3],b[j,3]);
55                              inc(i);dec(j);
56                         end;
57                until i>j;
58                if l<j then sort(l,j);
59                if i<r then sort(i,r);
60           end;
61 procedure dfs(x:longint);inline;
62           var p:point;
63           begin
64                p:=a[x];
65                while p<>nil do
66                      begin
67                           if d[0,p^.g]=0 then
68                              begin
69                                   d[0,p^.g]:=x;
70                                   e[0,p^.g]:=p^.w;
71                                   c[p^.g]:=c[x]+1;
72                                   dfs(p^.g);
73                              end;
74                           p:=p^.next;
75                      end;
76           end;
77 function max(x,y:longint):longint;inline;
78          begin
79               if x>y then max:=x else max:=y;
80          end;
81 function fatget(x,y:longint):longint;//inline;
82          var i:longint;
83          begin
84               i:=0;
85               while y>0 do
86                     begin
87                          if odd(y) then x:=d[i,x];
88                          inc(i);
89                          y:=y div 2;
90                     end;
91               exit(x);
92          end;
93 function getmax(x,y:longint):longint;//inline;
94          var i,j:longint;
95          begin
96               i:=0;j:=0;
97               while y>0 do
98                     begin
99                          if odd(y) then
100                             begin
101                                  j:=max(j,e[i,x]);
102                                  x:=d[i,x];
103                             end;
104                          inc(i);
105                          y:=y div 2;
106                     end;
107               exit(j);
108          end;
109 function getcom(x,y:longint):longint;//inline;
110          var i,j,k,l:longint;
111          begin
112               if x=y then exit(x);
113               if c[x]<c[y] then swap(x,y);
114               x:=fatget(x,c[x]-c[y]);
115               if x=y then exit(x);
116               i:=20;
117               while i>=0 do
118                     begin
119                          if d[i,x]<>d[i,y] then
120                             begin
121                                  x:=d[i,x];
122                                  y:=d[i,y];
123                             end;
124                          dec(i);
125                     end;
126               exit(d[0,x]);
127          end;
128 function getpath(x,y:longint):longint;//inline;
129          var i,j,k,l:longint;
130          begin
131               l:=getcom(x,y);
132               getpath:=max(getmax(x,c[x]-c[l]),getmax(y,c[y]-c[l]));
133          end;
134
135 begin
137      for i:=1 to n do a[i]:=nil;
138      for i:=1 to n do c[i]:=i;
139      for i:=1 to m do
141      sort(1,m);
142      j:=1;
143      for i:=1 to n-1 do
144          begin
145               while tog(b[j,1],b[j,2]) do inc(j);
148               merge(b[j,1],b[j,2]);
149          end;
150      fillchar(d,sizeof(d),0);
151      fillchar(c,sizeof(c),0);
152      d[0,1]:=-1;
153      dfs(1);
154      d[0,1]:=0;
155      for i:=1 to 20 do
156          begin
157               for j:=1 to n do
158                   begin
159                        d[i,j]:=d[i-1,d[i-1,j]];
160                        e[i,j]:=max(e[i-1,d[i-1,j]],e[i-1,j]);
161                   end;
162          end;
163      for i:=1 to t do
164          begin
166               writeln(getpath(j,k));
167          end;
168 end.
169               ```

0 条评论

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

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

• ### 2953: [Poi2002]商务旅行

2953: [Poi2002]商务旅行 Time Limit: 3 Sec  Memory Limit: 128 MB Submit: 8  Solved: 8...

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

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

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

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

• ### 2953: [Poi2002]商务旅行

2953: [Poi2002]商务旅行 Time Limit: 3 Sec  Memory Limit: 128 MB Submit: 8  Solved: 8...

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

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

• ### 3359: [Usaco2004 Jan]矩形

3359: [Usaco2004 Jan]矩形 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 8  Solv...

• ### Android Studio你不知道的快捷键(二)

在Android Studio你不知道的快捷键(一)里面，主要讲述了一些窗口操作的快捷键还有补全参数提示等，这一篇会分享一些代码代码编辑的快捷键。(默认Keym...

• ### linux学习第五十五篇： MySQL主从介绍，准备工作，配置主，配置从，测试主从同步

MySQL主从介绍 MySQL主从又叫做Replication、AB复制。简单讲就是A和B两台机器做主从后，在A上写数据，另外一台B也会跟着写数据，两者数据实时...