【萬萬沒想到 2025 年首更是這玩意】

 

一開始只是打算讓他處理一下題面信息，結果他自己開始了對題目的思考，并且想出來了。本人受到了極大的震撼，故予以記錄。
原題：https://codeforces.com/contest/1633/problem/E
以下為全文摘抄：

好的，我現在需要解決的問題是，給定一個包含n個點和m條邊的無向帶權圖，進行k次查詢。每次查詢給定一個整數qi，需要從圖中選出一棵生成樹，使得生成樹的所有邊的權值與qi的絕對差之和最小。對于前p次查詢，qi是直接給出的，之后的查詢則按照公式qi = (qi-1 * a + b) mod c生成。數據范圍中n比較小，但k可以達到1e7次，這提示我們需要一個高效的算法來處理大量查詢。

 

首先，我需要理解問題的核心：對于每個查詢qi，找到一棵生成樹，使得Σ|wj - qi|最小。這看起來像是一個優化問題，其中生成樹的選擇會影響總和的絕對差值?？紤]到n的范圍較小（<=50），而m可以達到300，生成樹的總數可能非常大，直接枚舉所有生成樹顯然不可行。

 

可能的思路是，對于每個qi，找到生成樹中邊權的中位數或某種接近qi的值，從而最小化絕對差之和。但生成樹的邊選擇需要滿足樹的連通性，這增加了問題的復雜性。

 

另一個角度是，絕對差之和的最小化類似于在生成樹中選擇邊權盡可能接近qi的邊?？赡艿膯栴}轉化為，如何選擇生成樹的結構，使得邊權的分布最優。不過，這樣的轉化可能并不直接幫助，因為生成樹的結構本身需要滿足連通性。

 

考慮到生成樹的邊權差異，或許可以將問題分解為：對于每個邊，根據當前qi，計算其權重|wj - qi|，然后在這個新的權重下尋找最小生成樹。也就是說，將原問題轉化為，對于每個qi，重新定義邊的權重為|wj - qi|，然后求這個新圖的最小生成樹的總權重。但這種方法的時間復雜度對于k次查詢來說是不可行的，因為每次查詢都需要重新計算所有邊的權重并運行最小生成樹算法，而k可以達到1e7次，這顯然無法在合理時間內完成。

 

因此，必須尋找一種更高效的預處理方法，或者找到某種數學規律，使得可以預先計算出所有可能的qi對應的最優生成樹的結構，從而在查詢時快速得到答案。

 

由于qi可能的值范圍很大（由于c可以達到1e8），直接預處理所有可能的qi是不現實的。因此，可能需要找到qi的分段區間，在每個區間內，最優生成樹的結構保持不變，從而只需要處理這些區間的邊界點，并在查詢時確定qi所在的區間，進而快速得到對應的總和。

 

這類似于離線處理所有可能的查詢，將qi排序后，確定每個區間對應的生成樹結構。然而，k可以達到1e7次，即使預處理也需要高效的方法。

 

另一種可能的思路是，觀察到對于絕對差之和的最小化，最優的生成樹可能對應某個特定的中位數附近的邊權。例如，當qi變化時，最優生成樹的邊選擇可能會在某個閾值處切換。因此，可能可以預先計算出所有可能的候選生成樹，并為每個生成樹確定其對應的qi區間，使得在該區間內該生成樹是最優的。

 

具體來說，假設我們枚舉所有可能的生成樹，對于每個生成樹T，計算使得Σ|wj(T) - qi|最小的qi區間。然后，對于每個查詢qi，只需找到對應的區間，從而得到對應的生成樹和總和。然而，生成樹的數量可能非常大（對于n=50，生成樹的數量是50^48級別），顯然無法枚舉。

 

因此，需要更聰明的優化方法?；蛟S，可以注意到對于不同的qi，最優生成樹的選擇可能遵循某種單調性，或者可以通過動態規劃或其他結構來管理可能的候選生成樹。

 

另一個角度是，考慮每條邊對于不同qi的貢獻。例如，對于邊權wj，當qi < wj時，絕對差為wj - qi；當qi >= wj時，絕對差為qi - wj。因此，總和Σ|wj - qi|可以分解為各個邊的分段線性函數。然后，整個問題轉化為在所有這些分段線性函數的疊加中，找到生成樹對應的函數的最小值。

 

然而，這似乎依然難以直接處理，因為生成樹的結構會影響哪些邊被選中，從而影響總和。因此，可能需要結合生成樹的選擇和qi的變化進行聯合分析。

 

或許，可以將問題轉換為對于每個可能的生成樹T，計算其對應的函數f_T(qi) = Σ|wj(T) - qi|，然后找到所有生成樹中f_T(qi)的最小值。這相當于在多個分段線性函數中尋找每個qi處的最小值。

 

如果能夠預先計算出所有可能的生成樹對應的f_T(qi)，然后對于每個qi，找到這些函數中的最小值，那么問題就解決了。但生成樹的數量太大，無法存儲所有函數。

 

因此，必須找到一種方法，在不顯式枚舉所有生成樹的情況下，確定對于給定的qi，哪個生成樹的f_T(qi)最小。

 

這里可能需要利用生成樹的結構性質。例如，在標準的最小生成樹問題中，Kruskal或Prim算法通過貪心選擇邊。也許在這個問題中，可以找到類似的貪心策略，根據qi的值動態調整邊的選擇。

 

例如，當qi增加時，邊權較低的邊可能變得更有優勢，因為|wj - qi|會增加對于高wj的邊，而減少對于低wj的邊。因此，生成樹的選擇可能會隨著qi的變化而切換不同的邊組合。

 

這提示可能存在一個關于qi的排序，使得當qi超過某個閾值時，生成樹的結構發生變化。如果能找到這些閾值，就可以將qi的整個范圍劃分為多個區間，每個區間對應一個最優生成樹。

 

但如何高效地找到這些閾值呢？這可能需要分析所有可能的生成樹之間的交叉點，即兩個生成樹T1和T2的f_T1(qi) = f_T2(qi)時的qi值。這些交叉點即為可能的閾值。

 

然而，這樣的交叉點數量可能非常大，尤其是當生成樹數量多時，這依然不可行。

 

另一種可能的思路是，對于每個查詢qi，最優生成樹實際上是在原圖中選擇邊權最接近qi的邊構成的生成樹。因此，可以預先按邊權排序，然后在查詢時根據qi選擇邊權接近的邊，構建生成樹。

 

但如何確保這些邊能構成生成樹，并且總絕對差最??？這可能需要類似于Kruskal算法的過程，但按|wj - qi|排序來選擇邊，同時保證連通性。

 

這似乎與標準的最小生成樹算法類似，只是邊的權重變為動態的|wj - qi|。如果每次查詢時都運行一次Kruskal算法，時間復雜度將是O(k * m log m)，對于k=1e7來說，這顯然無法接受。

 

因此，必須尋找一種預處理方法，使得對于不同的qi范圍，可以快速確定邊的選擇順序，從而避免每次查詢都重新計算。

 

觀察到邊的排序可能隨著qi的變化而變化。對于每條邊ej，其權重為|wj - qi|。當qi變化時，邊的排序可能會發生變化。特別是，當qi超過某個邊的wj時，該邊的權重會從遞減變為遞增，或者反之。

 

因此，邊的排序可能在qi的某些關鍵點發生變化。這些關鍵點是所有邊的wj值。當qi在相鄰的兩個wj之間時，邊的排序可能保持不變。因此，可以將整個qi的范圍劃分為多個區間，每個區間對應一種邊的排序方式。

 

對于每個這樣的區間，可以預先運行Kruskal算法，得到該區間內的最優生成樹，并記錄對應的總絕對差之和。然后，對于查詢qi，只需確定它屬于哪個區間，并直接取對應的總和。

 

這種方法的關鍵在于，區間的數量是O(m)，因為關鍵點是所有不同的wj值。排序后，這些關鍵點將分割整個數軸為m+1個區間。在每個區間內，邊的排序方式固定，因此可以預先為每個區間計算生成樹。

 

預處理步驟可能如下：

 

1. 收集所有邊的權值wj，排序并去重，得到關鍵點列表。

2. 將整個qi的范圍劃分為區間，基于這些關鍵點。

3. 對于每個區間，確定邊的排序（按|wj - qi|升序），然后運行Kruskal算法選擇生成樹，并計算總絕對差之和。

4. 對于每個查詢qi，找到其所在的區間，直接返回對應的總和。

 

然而，這里存在幾個問題：

 

- 邊的權值可能有很多重復，去重后關鍵點數量可能仍然很大（例如m=300，可能有300個關鍵點），導致預處理需要計算300次生成樹。對于每次生成樹計算，Kruskal的時間是O(m log m)，預處理總時間為O(m^2 log m)，這在m=300時是可行的（300^2=9e4，乘以log是約3e5，可以接受）。

- 對于每個區間，生成樹的結構可能不同，需要存儲每個區間的生成樹的總和函數，這可能是一個分段線性函數。例如，在區間[L, R]內，總和Σ|wj - qi|可能是一個關于qi的線性函數，可以表示為Σ(wj >= qi ? (wj - qi) : (qi - wj))。對于固定的生成樹邊集合，總和可以分解為對于每條邊的絕對差之和，這確實是一個分段線性函數，且在區間內可能具有固定的斜率。

 

因此，預處理步驟可以不僅存儲每個區間的總和值，還可以存儲對應的線性函數，從而在查詢時快速計算。

 

例如，對于某個區間[L, R]，假設生成樹T的邊集合為E_T，那么總和為Σ_{e∈E_T} |w_e - qi|。對于這個區間內的qi，可以將其分解為：

 

Σ_{e∈E_T, w_e <= qi} (qi - w_e) + Σ_{e∈E_T, w_e > qi} (w_e - qi)

 

這可以進一步表示為：

 

count_leq * qi - sum_leq + sum_gt - count_gt * qi

 

其中count_leq是E_T中w_e <= qi的邊的數量，sum_leq是這些邊的w_e之和；count_gt和sum_gt類似，對于w_e > qi的邊。

 

合并后，總和為：

 

(sum_gt - sum_leq) + (count_leq - count_gt) * qi

 

因此，對于每個區間，可以預先計算sum_gt, sum_leq, count_leq, count_gt，這些值在區間內是固定的（因為生成樹的邊集合固定，且在該區間內邊的排序方式固定，所以哪些邊在生成樹中是固定的）。然后，對于該區間內的qi，總和可以表示為線性函數a * qi + b，其中a = (count_leq - count_gt)，b = (sum_gt - sum_leq)。

 

因此，預處理步驟需要為每個區間存儲a和b，以及該區間的左右邊界L和R。當處理查詢時，只需確定qi所在的區間，然后用對應的a和b計算總和。

 

現在的問題是，如何生成這些區間和對應的線性函數。

 

具體步驟如下：

 

1. 收集所有邊的權值w_j，排序并去重，得到關鍵點列表S。例如，S = {s_0, s_1, ..., s_t}，其中s_0 = -infinity，s_{t+1}=+infinity，實際的關鍵點是所有w_j排序后的唯一值。

 

不過，實際上，當qi變化時，邊的排序方式可能變化的點不僅僅是邊的權值，因為當qi在兩個相鄰的w_j之間時，邊的排序可能保持穩定。例如，考慮兩條邊e1(w=5)和e2(w=10)。當qi在5和10之間時，|5 - qi|和|10 - qi|的順序取決于qi的具體位置。例如，當qi=7時，|5-7|=2，|10-7|=3，所以e1的權重更??；當qi=8時，|5-8|=3，|10-8|=2，此時e2的權重更小。因此，關鍵點可能在qi=7.5，即兩者的中點。這說明，邊的排序變化的臨界點不僅僅是邊的權值本身，還包括它們的中間點。

 

這大大增加了關鍵點的數量。例如，對于m條邊，兩兩之間的中點都可能成為關鍵點，導致關鍵點數量為O(m^2)，這在m=300時是9e4，預處理時間可能變得不可行。

 

這顯然不適用于m=300的情況，因為預處理需要處理9e4個區間，每個區間需要運行Kruskal算法，時間復雜度為O(m^3 log m)，這在時間上是不可接受的。

 

因此，這表明之前的思路可能不可行，需要尋找其他方法。

 

可能的另一種思路是，注意到在生成樹的選擇中，對于不同的qi，最優生成樹可能屬于某個特定的候選集合。例如，可能只有少數生成樹在不同的qi范圍內是最優的，因此可以預先找出這些候選生成樹，并確定它們的有效區間。

 

如何找到這些候選生成樹呢？這可能需要利用生成樹的性質，例如，最優生成樹在qi變化時可能只在某些特定點發生變化，而這些點與邊的權值有關。

 

或者，可以考慮將問題轉化為動態規劃，維護當前最優生成樹的結構，并在qi變化時調整。

 

然而，這些思路都較為模糊，需要更具體的方法。

 

回到問題本身，由于n較?。?lt;=50），但k很大，可能需要找到一個與qi無關的生成樹結構，或者利用某種數學性質快速計算總和的最小值。

 

例如，如果最優生成樹的總和Σ|wj - qi|的最小值等于某個與qi無關的結構，比如生成樹的中位數邊的權值，或者平均值，那么可能可以快速計算。但這種情況可能并不成立，因為生成樹的選擇會影響哪些邊被包含。

 

另一種可能：對于給定的生成樹，總和Σ|wj - qi|的最小值發生在qi等于生成樹邊權的中位數時。因此，可能最優生成樹的中位數盡可能接近qi。但如何選擇生成樹的中位數接近qi的生成樹呢？

 

這可能仍然無法直接解決問題，但或許可以結合生成樹的選擇和中位數的性質。

 

例如，對于每個生成樹，計算其中位數m_T，然后當qi接近m_T時，該生成樹可能是最優的。因此，預處理所有生成樹的中位數，并為每個可能的qi選擇最近的中位數對應的生成樹。

 

然而，生成樹的數量仍然太大，無法處理。

 

綜上，可能必須尋找一種近似的解決方案，或者找到問題中的某種特殊結構，使得可以高效處理大量查詢。

 

考慮到時間限制，可能需要尋找一種更聰明的觀察。

 

假設對于每個查詢qi，最優生成樹是原圖中按邊權與qi的絕對差排序后的最小生成樹。也就是說，對于每個qi，構造一個新圖，其中邊的權重為|wj - qi|，然后求這個新圖的最小生成樹，其總權重即為答案。

 

雖然直接這樣做的時間復雜度是O(k * m log m)，對于k=1e7不可行，但或許可以找到某種規律，使得可以預處理這些查詢。

 

注意到，后續的查詢qi是根據前一個查詢計算得到的：qi = (qi-1 * a + b) mod c。這可能意味著qi的值在某種循環中，或者可以通過某種數學方法批量處理這些查詢。

 

例如，如果a和c互質，那么qi可能會遍歷所有可能的值，但根據模運算的性質，可能需要找到循環節。但即使如此，對于c=1e8，循環節可能非常大，無法處理。

 

另一種可能性是，預處理所有可能的qi值，并將它們分類到不同的區間，然后對每個區間內的qi，計算對應的生成樹總和。但由于qi的范圍太大，這不可行。

 

回到之前的思路，如果預處理所有可能的邊排序的關鍵點，并計算每個區間對應的生成樹，那么對于每個查詢，只需要O(log m)的時間來確定區間，然后O(1)時間計算總和。

 

關鍵點的數量如果能夠控制在可接受的范圍內，例如O(m^2)，對于m=300是9e4，預處理需要9e4次Kruskal算法，每次O(m log m)時間，總預處理時間是9e4 * 300 * log 300 ≈ 9e4 * 300 * 8 ≈ 2.16e8操作，這可能在時間上是可行的，尤其是用高效的代碼實現。

 

然后，對于每個查詢，使用二分查找確定所在的區間，時間復雜度O(log m^2) = O(log 9e4) ≈ 17次操作，對于k=1e7次查詢，總時間為1.7e8操作，這應該是可以接受的。

 

因此，這可能是一個可行的方案。

 

具體步驟：

 

1. 收集所有邊的權值w_j，并生成所有可能的關鍵點，即所有w_j之間的中點。例如，對于每兩條邊e1(w1)和e2(w2)，如果w1 < w2，則關鍵點為(w1 + w2)/2。此外，還包括所有w_j本身，因為當qi等于某個w_j時，邊的排序可能發生變化。

 

2. 對所有這些關鍵點進行排序，去重，得到排序后的列表S。

 

3. 將整個qi的范圍劃分為區間，每個區間由相鄰的關鍵點確定。

 

4. 對每個區間，確定在該區間內的qi值時，邊的排序（按|wj - qi|升序），然后運行Kruskal算法選擇最小生成樹，并記錄該生成樹的邊集合。

 

5. 對于每個這樣的生成樹，預先計算其對應的線性函數參數a和b，即總和Σ|wj - qi| = a * qi + b，其中a和b在該區間內是固定的。

 

6. 對于查詢處理：

 

a. 對于前p次查詢，直接處理每個qi，通過二分查找找到它所在的區間，計算總和為a*qi + b。

 

b. 對于后續的查詢，生成qi后同樣處理。

 

然而，這里的關鍵問題是如何生成所有可能的關鍵點。例如，對于m條邊，兩兩之間的中點數量是O(m^2)，這在m=300時是大約45,000個中點，加上原有的300個w_j，總共約45,300個關鍵點。排序去重后，可能得到約相同數量的關鍵點。這將導致預處理需要處理約4e4個區間，每個區間運行一次Kruskal算法。

 

對于每個區間，運行Kruskal的時間是O(m log m)，總預處理時間為4e4 * 300 * log 300 ≈ 4e4 * 300 * 8 ≈ 9.6e7操作，這應該在合理范圍內，尤其是用高效的編程語言如C++實現。

 

一旦預處理完成，每個查詢的處理時間為O(log 4e4) ≈ 15次比較，加上計算線性函數的a*qi + b，這非?？臁?/p>

 

因此，這可能是一個可行的解決方案。

 

但需要注意以下幾點：

 

- 如何正確生成所有關鍵點，包括所有邊的w_j以及所有兩兩邊的中點。

 

- 在預處理每個區間時，確保邊的排序正確，即按|wj - qi|升序排列。由于在區間內qi的范圍是確定的，可以取區間內的任意一個值（例如中點）來排序邊。

 

- 處理生成樹時，可能在不同的區間中選擇相同的生成樹，此時可以合并這些區間以減少存儲。

 

此外，還需要注意，當多條邊具有相同的|wj - qi|值時，它們的相對順序可能影響Kruskal算法的選擇，但由于Kruskal在邊權相等時按輸入順序處理，可能需要穩定排序，或者在預處理時處理這種情況。

 

綜上所述，該方案的大致步驟如下：

 

預處理階段：

 

1. 收集所有邊的權值，生成所有關鍵點（邊的權值及兩兩邊權的中點）。

 

2. 排序并去重這些關鍵點，得到有序列表S。

 

3. 將數軸劃分為區間：[-inf, s_1), [s_1, s_2), ..., [s_{t-1}, s_t), [s_t, +inf)。

 

4. 對每個區間[L, R)，選擇一個代表值mid（例如(L + R)/2），計算所有邊的|wj - mid|，按此值升序排序邊。

 

5. 運行Kruskal算法，選擇最小生成樹，并記錄該生成樹的邊集合。

 

6. 對于該生成樹，計算其對應的線性函數參數a和b，其中a = (count_leq - count_gt)，b = (sum_gt - sum_leq)。這里，count_leq是生成樹中wj <= qi的邊數，sum_leq是這些邊的wj之和；count_gt和sum_gt類似。

 

實際上，a和b需要根據生成樹的邊集合和當前區間的qi范圍來確定。例如，在區間[L, R)內，假設生成樹的邊集合為E_T，對于該區間內的任何qi，每條邊e∈E_T的|w_e - qi|可以分解為：

 

- 如果w_e <= qi，則貢獻為qi - w_e → 對于總和的貢獻為 +1 * qi - w_e

 

- 如果w_e > qi，則貢獻為w_e - qi → 對于總和的貢獻為 -1 * qi + w_e

 

因此，總和可以表示為：

 

Σ (if w_e <= qi then qi - w_e else w_e - qi)

 

= Σ (qi - w_e) for w_e <= qi + Σ (w_e - qi) for w_e > qi

 

= (count_leq * qi - sum_leq) + (sum_gt - count_gt * qi)

 

= (count_leq - count_gt) * qi + (sum_gt - sum_leq)

 

因此，a = count_leq - count_gt，b = sum_gt - sum_leq。

 

其中，count_leq是E_T中w_e <= qi的邊數，sum_leq是這些邊的w_e之和；count_gt和sum_gt同理。

 

但是，在預處理時，由于區間[L, R)內的qi范圍已知，可以確定哪些邊的w_e <= qi對于所有qi在該區間內的情況。例如，如果區間的上界R是某個關鍵點，那么在區間內的qi的最大值可能小于等于某個值，從而可以確定哪些邊的w_e <= qi。

 

然而，這并不一定成立，因為區間可能包含多個w_e的值。例如，區間可能跨越多個邊的權值。

 

因此，可能需要更仔細的處理。實際上，對于每個區間[L, R)，可以確定在該區間內的qi的取值范圍，從而確定每條邊e的w_e與qi的關系：

 

對于邊e，如果w_e <= L，則對于所有qi >= L >= w_e，在區間[L, R)內，w_e <= qi。

 

如果w_e > R，則對于所有qi < R < w_e，在區間[L, R)內，w_e > qi.

 

如果w_e在[L, R)之間，則在該區間內，可能存在qi使得w_e <= qi或w_e > qi。例如，如果區間是[5, 10)，而w_e=7，則當qi在[5,7)時，w_e > qi；當qi在[7,10)時，w_e <= qi。因此，這樣的邊在該區間內會有一個分界點，導致該邊在區間內的不同部分有不同的貢獻。

 

這表明，之前的假設錯誤，即在一個區間內，邊的w_e與qi的關系可能不是固定的，因此無法預先確定count_leq和sum_leq等參數。

 

這導致之前的思路存在嚴重問題，因為無法在預處理時為整個區間確定a和b的固定值。

 

因此，必須重新考慮如何處理這種情況。

 

可能的解決方案是，將區間進一步細分，使得在每個子區間內，所有邊的w_e與qi的關系是確定的。例如，將區間劃分為更小的區間，使得在每個子區間內，對于所有邊e，要么w_e <= qi，要么w_e > qi。這可以通過將關鍵點包括所有邊的w_e值，以及所有兩兩邊的中點。

 

具體來說，關鍵點應包括：

 

- 所有邊的w_e值。

 

- 所有兩兩邊之間的中點，即(w_e1 + w_e2)/2，其中w_e1 < w_e2.

 

這些關鍵點將整個數軸劃分為區間，在每個區間內，所有邊的|w_e - qi|的相對順序是固定的，并且對于每條邊e，w_e <= qi或w_e > qi在區間內是確定的。

 

這可能嗎？

 

例如，對于兩條邊e1(w=5)和e2(w=10)，其中點7.5是關鍵點。當qi <7.5時，|5 - qi| < |10 - qi|；當qi >7.5時，|10 - qi| < |5 - qi|。因此，在區間劃分后，邊的排序在區間內是固定的。

 

同樣，對于邊e3(w=8)，在區間7.5到某個點之間，可能需要考慮其他邊的中點。

 

通過這樣的劃分，可以確保在每個區間內，邊的排序（按|wj - qi|升序）是固定的，并且每條邊的wj與qi的關系（<=或>）也是固定的。

 

這樣，對于每個區間，可以：

 

1. 確定所有邊在該區間內的|wj - qi|的排序。

 

2. 運行Kruskal算法按此排序選擇邊，得到生成樹。

 

3. 對于該生成樹，確定每條邊的wj與qi的關系（<=或>），從而計算a和b。

 

此時，由于在區間內，所有邊的wj與qi的關系是固定的（例如，在區間[L, R)內，對于某邊e，wj <= L → wj <= qi；wj >= R → wj > qi；若wj在[L, R)內，則必須在該區間的劃分中已經處理為子區間，使得在子區間內，wj <= qi或wj > qi）。

 

這似乎要求將區間進一步細分為更小的區間，以確保對于每條邊e，在子區間內，w_e <= qi或w_e > qi對所有qi在該子區間內成立。

 

因此，關鍵點應包括所有邊的w_e值，以及所有兩兩邊之間的中點。這將產生O(m^2)個關鍵點。

 

例如，對于m=300條邊，這樣的關鍵點數量是300 + 300*299/2 ≈ 45,000個關鍵點。排序去重后，可能得到類似數量的關鍵點。

 

然后，預處理每個區間，運行Kruskal算法，并計算對應的a和b。

 

這可能是一個可行的方案，盡管預處理時間可能較長。

 

綜上，最終的解決方案可能如下：

 

預處理階段：

 

1. 收集所有邊的權值w_j，生成所有關鍵點，包括：

 

a. 所有w_j的值。

 

b. 所有兩兩邊權的中點，即(w_i + w_j)/2，其中w_i < w_j。

 

2. 將這些關鍵點排序并去重，得到有序列表S。

 

3. 將數軸劃分為區間：[ -infty, S[0]), [S[0], S[1}), ..., [S[-2], S[-1}), [S[-1], +infty).

 

4. 對每個區間[L, R)：

 

a. 確定在該區間內的任意代表值mid（例如取(L + R)/2，注意處理無窮大）。

 

b. 計算每條邊e的|w_e - mid|，并按此值升序排序邊，作為Kruskal算法的輸入順序。

 

c. 運行Kruskal算法，選擇生成樹T。

 

d. 對于生成樹T中的每條邊e，確定在該區間內，w_e與qi的關系：

 

- 如果w_e <= L，則對于所有qi in [L, R)，w_e <= qi。

 

- 如果w_e >= R，則對于所有qi in [L, R)，w_e > qi.

 

- 如果L < w_e < R，則由于關鍵點包括所有邊的w_e，區間必然被分割為更小的區間，因此在當前預處理階段，該情況已經被處理。因此，在當前的區間[L, R)中，w_e要么 <= L，要么 >= R。

 

因此，在預處理時，對于當前區間，所有邊的w_e與qi的關系是確定的，即要么w_e <= qi，要么w_e > qi。

 

e. 根據生成樹T中的邊，計算count_leq（w_e <= qi的邊數）和sum_leq（這些邊的w_e之和），以及count_gt和sum_gt。

 

f. 存儲該區間對應的a = count_leq - count_gt，b = sum_gt - sum_leq。

 

查詢處理階段：

 

對于每個查詢qi：

 

1. 使用二分查找在S中找到qi所在的區間。

 

2. 獲取該區間對應的a和b。

 

3. 計算總和為a * qi + b。

 

然而，需要注意，當L或R為無窮大時，需要特殊處理。例如，當區間是[-inf, s_0)，此時所有qi < s_0，因此對于所有邊e，如果w_e >= s_0，則w_e > qi；如果w_e < s_0，則可能在當前區間內存在w_e > qi的情況，這需要重新驗證。

 

這表明，之前的假設可能不成立，因為即使關鍵點包括所有w_e和中點，某些邊的w_e可能在區間內，導致w_e與qi的關系不確定。例如，假設區間是[5, 7)，而某條邊的w_e=6，那么對于qi=5.5，w_e=6 > qi；對于qi=6.5，w_e=6 <= qi？不，6 <= qi=6.5是true。但區間[5,7)中的qi可能在5到7之間，因此對于w_e=6，當qi在[5,6)時，w_e > qi；當qi在[6,7)時，w_e <= qi。因此，該邊在區間[5,7)中的不同子區間內，其與qi的關系會發生變化。

 

這意味著，之前的預處理步驟未能正確細分區間，導致在一個預處理區間內，某條邊的w_e與qi的關系可能變化。這表明，關鍵點必須包括所有邊的w_e，而不僅僅是中點。例如，在上面的例子中，關鍵點應包括w_e=6，將區間[5,7)分割為[5,6)和[6,7)。

 

因此，正確的關鍵點生成應包括：

 

所有邊的w_e值，以及所有兩兩邊權的中點（w_i + w_j)/2，其中w_i < w_j。

 

這將確保在每個預處理區間內，所有邊的w_e要么全部 <= qi，要么全部 > qi，因為區間的邊界是這些關鍵點。例如，考慮邊e的w_e=6，如果區間是[5,6)，則對于所有qi in [5,6)，w_e=6 > qi；如果區間是[6,7)，則w_e=6 <= qi。

 

因此，正確的預處理步驟如下：

 

預處理階段：

 

1. 收集所有邊的權值w_j，生成所有關鍵點：

 

a. 所有邊的w_j。

 

b. 所有兩兩邊權的中點，即(w_i + w_j)/2，其中w_i < w_j。

 

2. 對這些關鍵點進行排序并去重，得到有序列表S。

 

3. 將數軸劃分為區間：[-inf, S[0]), [S[0], S[1}), ..., [S[-2], S[-1}), [S[-1], +inf).

 

4. 對每個區間[L, R)：

 

a. 確定該區間內的代表值mid，例如取(L + R)/2。如果L是-inf，取一個足夠小的值；如果R是+inf，取一個足夠大的值。

 

b. 計算每條邊e的|w_e - mid|，并按此值升序排序邊。

 

c. 運行Kruskal算法，選擇生成樹T。

 

d. 對于生成樹T中的每條邊e，確定在該區間內，w_e與qi的關系：

 

- 如果w_e <= L，則對于所有qi in [L, R)，w_e <= qi（因為區間的右端點R可能大于w_e，但關鍵點包括所有w_e，所以如果w_e <= L，那么R > L >= w_e，因此對于qi >= L >= w_e，w_e <= qi）。

 

- 如果w_e >= R，則對于所有qi in [L, R)，w_e > qi（因為qi < R <= w_e）。

 

- 如果L < w_e < R，則由于關鍵點包括w_e，區間必然被分割為[L, w_e)和[w_e, R)，因此當前處理的區間[L, R)實際上不包含w_e，即R <= w_e或L >= w_e。否則，在生成關鍵點時，w_e會被加入，導致區間分割。

 

因此，在當前區間[L, R)中，對于任何邊e，要么w_e <= L，要么w_e >= R，從而在區間內的所有qi，w_e與qi的關系是確定的。

 

e. 計算生成樹T中的count_leq（w_e <= qi的邊數）和sum_leq，count_gt（w_e > qi的邊數）和sum_gt。

 

f. 存儲該區間的a = count_leq - count_gt，b = sum_gt - sum_leq.

 

查詢處理：

 

對于每個查詢qi：

 

1. 使用二分查找找到qi所在的區間。

 

2. 獲取該區間的a和b。

 

3. 總和為a * qi + b.

 

這樣，預處理階段確保了在每個區間內，生成樹T的邊集合固定，并且每條邊的w_e與qi的關系是確定的，從而可以正確計算a和b。

 

現在，關鍵問題是如何高效生成所有關鍵點，并確保預處理正確。

 

例如，對于m=300條邊，生成所有w_j（300個）和所有中點（約45,000個），總關鍵點數量約為45,300個。排序和去重后，假設剩下約同樣數量。

 

預處理每個區間需要運行Kruskal算法，時間復雜度為O(m log m) per interval，總預處理時間約為45,300 * 300 * log 300 ≈ 45,300 * 300 * 8 ≈ 1.087e8操作，這在C++中是可行的。

 

對于查詢階段，每個查詢需要O(log 45,300) ≈ 16次比較，加上一次乘法和一次加法，總時間對于1e7次查詢來說是可行的。

 

因此，這似乎是解決問題的正確方法。

 

最后，處理后續查詢時，由于qi可能由前一個查詢生成，需要按照題目給出的遞推公式計算，并確保模運算的正確性。

 

綜上，該問題的解決方案包括：

 

1. 預處理所有可能的關鍵點，生成區間。

 

2. 對每個區間計算對應的生成樹和線性函數參數。

 

3. 對每個查詢，快速定位區間并計算結果。


【分割線】
最幽默的是以上只是思考過程，Deepseek 最終給出的解答如下：

[file name]: 1.txt  
[file content begin] 
給定一個包含 $n$ 個點和 $m$ 條邊的無向帶權圖，你有 $k$ 次詢問，第 $i$ 次詢問給定一個整數 $q_i$，你需要從圖中選出一棵生成樹，設該生成樹的 $n-1$ 條邊的權值為 $w_1,w_2,\dots,w_{n-1}$，你需要求出 $\sum\limits_{j=1}^{n-1}|w_j-q_i|$ 的最小值。  

該題所有 $k$ 次詢問中，前 $p$ 次詢問的 $q_1,q_2,\dots,q_p$ 在輸入中給定，從第 $p+1$ 次詢問開始的 $q_i=(q_{i-1}\cdot a+b)\bmod c$。  

數據范圍：  

- $2\leqslant n\leqslant 50$，$n-1\leqslant m\leqslant 300$，$1\leqslant p\leqslant 10^5$，$p\leqslant k\leqslant 10^7$，$0\leqslant a,b\leqslant 10^8$，$1\leqslant c\leqslant 10^8$。  
- $0\leqslant w_i\leqslant 10^8$。  

[file content end]