UOJ Logo

NOI.AC

2S 512MB

#104. 直径

统计

题目描述

​ 老虎和蒜头是好朋友。

​ 老虎最近学习了树的直径问题。众所周知,对于正权的图,我们可以通过两遍 BFS 在 $ O(n) $ 的时间复杂度解决树的直径问题。蒜头是一个热爱思考的好孩子,他想要知道,对于一张给定的无向图,若定义直径为图中最远的两点间的距离,那么该图的直径是多少?

​ 下面我们具体描述该无向图。一条长度为 $ l $ 的链是由 $ M \rightarrow \infty $ 个点构成的,且在第 $ i $ 个点和第 $ i + 1 $ 个点之间有一条长度为 $ \frac{l}{M} $ 的边。该无向图由 $ n $ 条长度分别为 $ a_i $ 的链、以及 $ m $ 条链与链之间的连边构成。链与链之间的连边按照如下方式描述: 第 $ s_1 $ 条链上离左端点距离为 $ l_1 $ 的点和第 $ s_2 $ 条链上离左端点距离为 $ l_2 $ 的点之间存在一条边权为 $ 0 $ 的连边。注意,这里的 $ s_1, s_2 $ 可能相同。我们保证图是联通的。

输入格式

​ 输入的第一行包括两个正整数 $ n, m $ ,表示链的条数和链与链之间连边的条数。

​ 接下来一行 $ n $ 个正整数 $ a_i $ ,表示第 $ i $ 条链的长度。

​ 接下来第 $ m $ 行,每行四个整数 $ s_1, l_1, s_2, l_2 $ 。

输出格式

​ 对于每组询问,输出一行一个实数,表示该无向图的直径。

样例

样例一

input

2 1
10 6
1 3 2 1

output

12

explanation

样例二

input

1 1
10
1 1 1 8

output

5.5

explanation

样例三至样例六

见样例数据下载

数据范围及限制

对于 100% 的数据,$ n, m \le 500, 0 \le l_i \le a_{s_i}, a_i \le 10^{12} $ 。

本题采用子任务测试。

Subtask 1[10 points]: $ n, m, a_i \le 5 $

Subtask 2[20 points]: $ n, a_i \le 20, m \le 200 $

Subtask 3[30 points]: $n, m \le 200$

Subtask 4[40 points]: 无特殊限制。

时间限制: 2s

空间限制: 512MB

样例数据下载