摘要： 原題鏈接：貨車運輸 kruskal重構樹+LCA做法，樹剖不想寫 很容易發現原圖跑最短路可以解，但是復雜度難以承受，所以考慮如何簡化該圖。 發現原圖邊權維護的應該是（u，v）的最小值，并且最優選擇是這個最小值最大，所以如果有多條（u，v),只保留最大的沒有影響，如果我們維護一棵最大生成樹就一定包含（ 閱讀全文