在派桑地區有N個城市，當地交通建設的成本很高，所以只有N - 1條道路，已知每條道路連接兩個不同的城市，而且任何兩個城市之間都還是有道路可以直接或間接到達。爪哇公司有K位銷售員，每位銷售員必須走訪若干個城市去執行他的任務，因為這是一個周期性的工作而且爪哇公司在每一個城市都有宿舍，所以每一位銷售員可以從任何一個城市開始，而完成他的拜訪任務後也不必回到起點。為了節省旅行成本，爪哇公司委託丙正正程式設計公司來幫忙規劃每一位銷售員的行程，身為丙正正公司的程式設計師，你的任務是要計算出所有銷售員所走的最小路程總和是多少。請注意每個銷售員所需拜訪的城市可能有重複，但是他們的任務是彼此獨立而無關的。
上圖展示一個範例，其中圖(a)顯示了8個城市與7條道路的資訊。假設K=2，也就是有兩位銷售員，而S1={3,5}以及S2={7,2,1,5,6}分別代表第一位與第二位銷售員需要拜訪的城市集合。圖(b)與(c)分別是這兩位銷售員必須走過的道路與城市，我們可以發現，第一位銷售員所需走的最短路程是從3走到5(或是5走到3)，其長度是6，也就所經過的道路長總和；而第二位銷售員的最短路徑則是6->1->5->1->0->7->0->2，其長度是16。所以這個範例的最短總路程是6+16=22。此範例即為下面的範例1。
測試資料的第一行是兩個整數N與K，2 ≤ N ≤ 100,000，1 ≤ K ≤ N，分別代表城市與銷售員的數量，每個城市都以一個0 ~ N-1的整數來編號。接下來N-1行是道路資訊，每一行有三個整數a、b與w，代表一條道路連接城市a與b，而其長度為w，其中0≤ a, b < N且w是不超過1000的正整數。在道路資訊後接著的是每個銷售員需要拜訪的城市，以下第i行是第i位銷售員需要拜訪的城市集合Si，該行的第一個數字是該集合的城市數量 |Si|，接著是|Si|個城市編號。我們假設所有銷售員所需拜訪的城市數量總和$\color{black}{\sum_{i=1}^{N-1}{|S_i|} \le 2N}$。輸入資料同一行的數字間皆以空白隔開。
輸出所有銷售員所需要經過的最短路程總和。請注意答案可能超過232，但不會超過260。
範例輸入 1： 8 2 6 1 4 1 4 1 1 5 1 1 0 3 0 2 5 3 0 2 0 7 1 2 3 5 5 7 2 1 5 6 範例輸入 2： 5 3 0 1 3 1 2 1 3 2 5 4 3 2 3 1 2 3 3 0 4 2 4 3 2 1 4
範例輸出 1： 22 範例輸出 2： 25
本題共有四個子題，每一子題可有多筆測試資料：
第一子題，N ≤ 100，解出可以獲得 17 分；
第二子題，| Si | = 2，對每一個1 ≤ i ≤ K。解出可以獲得 11 分；
第三子題，| Si | = 4，對每一個1 ≤ i ≤ K。解出可以獲得 10 分；
第四子題，無額外限制。解出可以獲得 62 分。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||