對每間房子，可以花 O(m) 的時間求出與所有捷運站的距離，並記錄最小值。 接著再將所有房子依照記錄好的距離最小值、房租以及房子編號排序，時間為 O(nm + m log m)。
這題的座標範圍很大，在記錄距離最小值的時候要很小心別將 INF 的範圍開太小。
為了簡化問題我們可以將所有答案乘以 2。 換句話說兩個數字的平均視為兩數字總和，一個數字的平均也一樣可以視為該數字本身的兩倍積。
下面四個算法的共同點都是先把所有的數字選法，也就是滿足 i ≤ j 的 wi + wj 全部建出來找第 k 大。
[算法1]: 將數字全部排序輸出第 k 大，複雜度為 O(n2 log n)。
[算法2]: 將數字丟到一個 priority_queue 裡面並維護目前為止的前 k 大。 換句話講，當 priority_queue 的大小比 k 大時就將最小的數字 pop 掉，如此可以在 O(n2 log k) 的時間維護前 k 大數。
[算法3]: 將數字的值建出以後用線性找第 k 大的方法。 STL library 裡面有提供線性的 nth_element 可以使用，自己實作 Quickselect 或 Introselect 也可以分別達到平均 O(n2) 或最差 O(n2) 的效率。
[算法4]: 將數字的值建出以後線性 make_heap，並將最大值 pop k 次即可得到第 k 大。 這樣做的複雜度是 O(n2 + k log n)，在 k 很大的時候可以視為是 O(n2 log n)。
n=10000 的時候 O(n2) 保證可以通過所有的測資，但 O(n2 log n) 則沒有這個保證，只有常數小的解可以通過。
首先將 w 排序由小排到大，並將所有的 wi + wj 依照 j-i 分成 n 組:
可以用一個最大堆（或 priority_queue），一開始將每一組裡最前面的數字丟進 heap 裡。 接著連續 pop k 次，每次 pop 完最大的數字後將該數字所屬組別的下一個數字繼續放進 heap 裡。 由於 w 有排序過，可以保證每一組的數字都是從大排到小，上述方法在經過 pop k 次的過程後可以正確得到第 k 大總和。
複雜度為 O(k log n + n log n)，可以通過所有 k ≤ 200,000 的子任務。
二分搜尋答案 C，每次判斷「是否有 k 組數字總和 ≤ C」。
判定性問題的部分，若預先將所有數字排序後可以簡單的用雙指標維護 wi + wj ≤ C 的 j 的範圍， 複雜度為 O(n log w + n log n)，可以通過所有子任務。
簡而言之，這題就是將「樹上最長路, 樹的直徑」這個經典題做了以下的修改：
比起正確的作法，值得一提的是因為條件的設定這題存在許多錯誤的做法：
這些演算法的限制十分容易混淆，而且比賽中一旦陷入錯誤的做法通常會很難跳脫。 筆者這裡建議大家學演算法的時候要多留意證明的過程，以避免陷入用錯誤演算法而無法跳脫的死胡同。
在挑選某個點作為 root 以後可以 DP 紀錄兩個表格:
down[i]: 以 i 為起點，往下到某個點的最長路徑dp[i]: 以 i 為 root 的子樹中最長的路徑其中 dp[i] 可以由下面幾種狀況轉移過來:
dp[i] = dp[c]，c 是 i 的某個兒子dp[i] = w[i] + down[c], c 是 i 的某個兒子dp[i] = w[i] + down[c1] + down[c2], c1, c2 是 i 的某兩個兒子可以在線性時間內求出每棵子樹的最長路。
把環上的每個點看成是很多棵樹的 root 串聯起來，依照最長路經過的非樹根節點可以分類成兩種情況:
(1) 的部分可以對每棵樹做一次 DP 在線性求出來，
(2) 的部分可以算出每棵樹 down 值後在環上再做一次 DP，DP 的值可以用前綴和 + deque 或 set 維護。
最快的作法一樣可以在線性的時間算完。
從左至右枚舉字串的每個字元，可以定出以下狀態: dp[f1][f2][a][b][c][suf][b2][b1] = v，其中:
狀態數的大小為 24 * (a+1) * (b+1) * (c+1) * (a+b+c+1)。 每次轉移枚舉下一個字元 b0 時，環狀字串中的字元 b1, b0, f1 會分別變成與字元對 (b2, b0), (b1, f1), (b0, f2) 相鄰。 則可以重新計算轉移後下一個字串的狀態值與最長連續字元數，複雜度為 O(abc * (a+b+c))。
要注意的是由於 DP 的維度很高不好優化 cache locality，所以計算速度比一般的 DP 還慢許多。 在我們的實作中計算 a, b, c ≤ 60 的表格約只需要跑過 1300 萬個狀態，但卻需要 2 秒左右的時間。
在介紹引理之前我們先令 $C_X$, $C_Y$ 分別為環狀字串中 X 與 Y 的數量。
並且注意以下所提到的字串都是以環狀字串為前提。
考慮將 $a$ 個 (X, X)， $b$ 個 (Y, Y) 以及 $c$ 個 (X, Y) pair 裡的字元展開，會產生 $2a$ 個 X 字元、
$2b$ 個 Y 字元，以及 $c$ 個 X 與 Y 字元。
這些字元加起來剛好會把字串中每個字元算到兩次，因此可以得到：
也就是：
可以注意到一個字串算出來的 $c$ 值必須是偶數，這是因為 (X, Y) pair 的對稱性。
若有一個字元前面為 X 後面為 Y，
則一定可以找到一個相對應的字元前面為 Y 後面為 X。
換句話說，在 $c$ 個與 (X, Y) 相鄰的字元裡，恰好會有 $\frac{c}{2}$ 的字元前面為 X 後面為 Y，
並且有 $\frac{c}{2}$ 的字元前面為 Y 後面為 X。
[引理]: 構造一符合題目所求條件的字串時，只要 X, Y 字元數分別為 $C_X$ 與 $C_Y$ ，並同時滿足 $a, b, c$ 的任一 pair 條件，
則另外兩條件也一定會符合。
[範例]: 這個性質有點抽象，我們用比較具體的例子來說明。 假設要構造一 $(a, b, c) = (5, 1, 4)$ 的字串，根據引理1的公式可以得到 $C_X=7, C_Y=3$。
我們構造一字串需要滿足 a, b, c 其中一條件即可，這裡用 b 條件來當例子。
首先把 b=1 個 (Y, Y) pair 的位置決定好後：
___Y_Y____
根據 X 與 Y 的數量條件，可以得知剩下的 8 個空格需要填入 7 個 X 與 1 個 Y。
剩下的這 8 個字母只要在不增加 (Y, Y) pair的前提下無論用何種順序填入，
得出來的字串 (X, X) 與 (X, Y) 相鄰字元數會分別是 $a$ 與 $c$。
[說明]: 這個性質可以簡單地從引理1說明，若把引理1中的 $C_X, C_Y$ 想成一聯立方程式的兩常數，$a, b, c$ 為變數。 不難推出當 $a, b, c$ 中若有一個值決定時另外兩個變數的解必然唯一。
這個引理看似沒什麼意義，卻可以給我們一個可以簡化構造難度的方向： 比起考慮相鄰條件的限制，我們可以換成考慮字元的數量，如此可以降低構造時思考的難度。
由對稱性以下我們可以假設 $C_X \ge C_Y$ 來簡化問題。
（若 $C_X < C_Y$，可以將 $C_X, C_Y$ 以及 $a, b$ 交換，求出來的字串 X, Y 字元反轉即可得到原所求字串）
（存在性）： 構造一個字串，將所有的 X 字元用 Y 當隔板盡量平均分散，構造出來的字串不穩定度恰為 $\lceil \frac{C_X}{C_Y} \rceil$ 且合乎所求。
例如 $C_X=7, C_Y=2$，可以構造出字串 XXXYXXY。
引理的條件給出 $\frac{C_X}{C_Y} \ge 2$，可以保證任意兩個 Y 之間的距離大於等於 2，
所以構造出來的字串符合 $b=0$ 的條件。
根據引理2，由於 b 條件被滿足了，所以 a, c 也必定為正確數值。
（答案下界）： 將構造的環狀字串中連續的 X 視為一個區間，因為只有 $C_Y$ 個 Y 而已，字串至多只有 $C_Y$ 個連續的 X 區間。
由鴿籠原理，至少有一個區間的 X 個數大於等於 $\lceil \frac{C_X}{C_Y} \rceil$。
由以上兩點，我們可以證明此構造法構造出的字串為最小可能的不穩定度。 這個引理得出的構造法為 $2a \ge c, b=0$ 子任務的預設做法。
可以把連續相同字母壓縮起來，由對稱性我們可以以以下表示法表示任意答案字串：
$X^{a_1}Y^{b_1}X^{a_2}Y^{b_2} \cdots X^{a_t}Y^{b_t}$
在這裡可以觀察到幾個性質:
X, Y 拿一個出來放在最後，(a, b, c) 不變且不穩定度有可能變小
思考上面兩性質對應到的 (a, b, c) 時，可以加入引理2的結論來思考會簡化許多 ー 例如只考慮構造出來字串中 (Y, Y) 的 pair 數量，b 可以用 $\sum \max(0, b_i - 2)$ + 「$a_i=1$ 的數量」來計算。
由上面的結論可以發現，{a} 與 {b} 必定有一個集合只有 1, 2 兩種數字而已， 由於 $C_X \ge C_Y$，可以假設只有 1, 2 數字的集合是 {b}。 試著枚舉 {b} 集合中 $b_i = 2$ 的數量 $P_{yy}$ 與 $b_i = 1$ 的數量 $P_y$； 可以推出關係式 $2P_{yy} + P_y = b + \frac{c}{2}$（引理1）， 這代表我們可以在 O(b+c) 的時間內枚舉所有 $P_{yy}$ 與 $P_y$ 的組合。
枚舉完 $P_{yy}$ 與 $P_y$ 之後，接著需要構造恰好 $b$ 個 $a_i=1$， 以及其他必須都要大於等於 2 的 $a_i$，剩下的 $a_i$ 只要都大於等於 2 必定是合法的解（引理3, 引理2）， 只需要盡量讓最大值越小越好盡量最小化字串不穩定度就可以了。
以下給出上面引理4所得出的算法：
X 與 Y 該有的個數(Y, Y) pairs 的位置以及各字元數量Y 都是連續 1 個或 2 個，可以線性枚舉數量
X 只有 $b$ 個，其他的 X 盡量平分且每個區塊都至少要有兩個如果要得到滿分的話還得需要考慮更多構造法沒辦法處理的 edge cases， 在這裡我們就列出一些特殊解的做法以供參考。
無解的 case:
特殊解的 case:
X 或 Y 一種字元若僅觀察出性質 1 的話，由於子任務 1 保證公路長度都是 $1$，因此只需要判斷是否存在一條邊移除後會使得 $u, v$ 不連通即可。
在本子任務可以 $O(m)$ 枚舉邊、$O(n + m)$ 的簡單遍歷圖來得出答案，總時間複雜度會是 $O(qm(n + m))$，可以在時限內通過。當然也可以使用 Tarjan 的 dfs tree 找橋算法可以輕易的在經過 $O(n + m)$ 時間的預處理後，維護好所有的 BCC，$O(1)$ 的直接回答詢問。
繼承子任務 1，考慮由小到大枚舉答案的話，由於只有至多 $m$ 種不同的邊權，因此只要 $O(m)$ 窮舉後，利用 Tarjan 的 dfs tree 找橋算法就可以在 $O(n+m)$ 的時間做檢查。
當然，若每筆詢問都重新窮舉一遍、跑一遍 Tarjan 演算法的話勢必會 TLE，此時有兩種路線可以進行優化：
事先把所有詢問讀進來後，只做一次枚舉答案的過程，每次窮舉新的邊權、跑完 Tarjan 演算法後就暴力讓每一筆詢問檢查詢問的 $u, v$ 是否已經在同一個 BCC 內，取最早的時間點即是答案。
總時間複雜度會是 $O(m(n + m + q))$。
觀察到「最大公路長度最小」這件事本身就是一個常見的對答案二分搜題型，可以每筆詢問直接對答案二分搜後，用 Tarjan 演算法 $O(n + m)$ 檢查即可。
時間複雜度可以是 $O(q(n+m)\log C)$ 或 $O(q(n + m)\log m)$，前者是假定值域是 $C$ 時直接對值域做搜尋、後者是只特別針對至少 $m$ 種不同的邊權做搜尋，本子任務的範圍有刻意讓兩者都可以通過。
比較子任務 2 的兩種做法後，可以將「離線回答」與「對答案二分搜」做結合，發現在離線回答是我們也只是枚舉 $O(m)$ 種答案而已，每次枚舉完都會有一個 $O(n)$ 的 BCC 資訊需要做儲存。因此，可以直接把這部分當成預處理，把 $O(m)$ 種版本的 BCC 資訊全部存下來，對於每筆詢問在存好的資訊上使用二分搜找到解答。
總時間複雜度優化至 $O(m(n + m) + q\log m)$。
觀察到由小到大枚舉邊權的過程，其實就是要試圖維護類似「動態加邊、動態維護 BCC 關係」的資訊，但動態維護可能過於複雜，我們退一步來試圖觀察加邊的過程。
注意到當兩點 $u, v$ 一旦連通後，再加更多邊他們也會連通；同樣的性質也適用於 BCC 的關係，當兩點 $u, v$ 一旦屬於同一個 BCC 後，再加更多邊他們也會屬於同一個 BCC。
因此，我們可以把邊分成以下三種：
此時又有兩種不同的路線可以進行優化：
由於我們只需要 BCC 的資訊，如果 BCC 的關係沒有改變，那我們沒有任何必要特別處理，同時又可以觀察到，BCC 只會不斷進行合併，也就是頂多只會有 $n-1$ 次的事件發生（$n-1$ 次後勢必全部的點都會被合併成一個 BCC）。
因此，透過上述邊的分類，遇到非第二種邊的時候就不跑 Tarjan 演算法重新獲得 BCC 的資訊，就可以將 Tarjan 演算法的執行次數縮減到 $O(n)$ 次，總時間複雜度就是 $O(m\log m + n^2 + q\log m)$，可以通過本題。
判斷邊的種類時，可以再多紀錄連通性資訊來判斷是否是第一種邊，觀察到第一種邊其實也只有 $O(n)$ 條，除了用並查集動態維護連通性外，實作上如果不特別細分第一、二種邊或是遇到第一種邊時重新遍歷圖維護連通性都還是可以在相同的時間複雜度內通過本題。
而第三種邊只要看邊的兩點是否都已經在 BCC 內就可以 $O(1)$ 進行判斷。
更直接一點的話，我們可以把所有可能是第一種和第二種邊的邊集找出來。
實際上可以輕易的發現第一種邊就是整張圖的一棵最小生成樹；同理，將最小生成樹找出來從原圖移除第一種邊後，再找出一個最小生成森林就是第二種邊了（那些進不去生成森林的邊只會形成不必要的環）。
因此可以很乾脆的將邊數在兩次最小生成樹演算法後縮減至 $O(n)$ 條並套用子任務 3 的演算法，總時間複雜度同樣是 $O(m\log m + n^2 + q\log m)$，可以通過本題。
由於考慮到初選的題目難度控制，本題只有將範圍出到 $n$ 至多 $1000$，事實上我們可以再進一步的找到時間複雜度更理想的做法。
繼承子任務 4 提到減少邊數的想法，我們可以跑一遍最小生成樹找出第一種邊後，蓋好這棵樹，觀察第二種邊在上面改變的資訊。
注意到其實每次我們都是加一條邊進去樹上後，將樹上與其形成環的路徑全部縮成一個 BCC，因此只要有一個例如並查集的資料結構來負責幫忙「跳過」那些已經合併起來的點，就可以在均攤 $O(n\alpha(n))$ 的時間內完成 BCC 全程的維護。具體做法會是將最小生成樹拉成有根樹後，試圖紀錄每個 BCC 內在樹上深度最淺的點，加一條邊 $u, v$ 時如果找出 $u, v$ 各自 BCC 內深度最淺的點中較深的那個點，將他和自己的父親做合併，反覆進行就可以完成 $u, v$ 路徑上的合併。
只要利用持久化陣列就可以在 $O(n\log^2 n + q\log\log n\log n + m\log m)$ 的時間試圖通過本題，又或者是可以試著利用整體二分搜演算法設計出 $O(n\alpha(n)\log n + m\log m + q\log n)$ 的做法，但兩者實作量都略大，以下再介紹第三種路線。
有趣的是，我們其實可以造出一個帶邊權的森林 $T$，使得：
這個森林 $T$ 其實蓋起來也相當的簡單，回想前面暴力用並查集合併 BCC 的過程，只要在加進邊權 $l$ 的邊、需要合併兩個 BCC 時，在 BCC 的兩邊各挑一個點，假設分別叫其 $a, b$，並在 $T$ 中加入 $a, b$ 這條邊、權重為 $l$ 即可。
實作上當然可以在蓋完樹之後再次實作例如 LCA 的演算法求出兩點路徑上的最大值，但如果利用啟發式合併實作並查集，就可以蓋出一個高度量級為 $O(\log n)$ 的樹，詢問時暴力在樹上爬出路徑就可以找到該最大值了。
總時間複雜度最終是 $O((n + m + q)\log n + m\log m)$，實作起來其實意外的簡單。