題面

【錯解】

最大最小？最小生成樹嘛

蛤？還要求和？

點分治？

不可做啊

寫了個MST+暴力LCA，30pts，140多行

事后發現30分是給dijkstra的

woc

【正解】

樹上計數問題：①并查集②啟發式合并③點分治

其實可以啟發式合并

跑一遍Kruscal，每次用數據結構維護滿足條件的點對再乘上當前這條邊的權值。因為排了序，所以這條邊是最大的

復雜度大概\(O(MlogM+Nlog_N^2)\)

代碼

轉載于:https://www.cnblogs.com/lstoi/p/9861076.html

總結

以上是生活随笔為你收集整理的【20181026T2】**图【最小瓶颈路+非旋Treap+启发式合并】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。