【線上程式設計産品介紹】
阿裡雲開發者社群線上程式設計：
免費刷題大神器，助你拿到好offer
周賽月賽不停歇，做題還能領獎品
大賽筆試全真題，常做常新有驚喜
點選連結開始産品體驗：
https://developer.aliyun.com/coding 本文為大家介紹的是“123.Codancer的旅行”的解法探究。先來看一下題目内容：題目詳情
題目等級：困難
知識點：二分查找/并查集/貪心
檢視題目：123.Codancer的旅行期末考試終于結束啦，Codancer開始了他的旅行。
現在整個地圖上由n個城市，這些城市之間有n-1條道路相連，每條道路都有一個距離，并且保證整個圖是連通的，即這個地圖可以看作是一棵樹。
現在假設Codancer要從城市A到城市B，那麼他的路費就是從A-B的路徑上邊權最大的邊的權值wmaxx元。
現在Codancer有k元，他想知道他能選擇那些(A,B)并且A
<
B使得codancer能夠到達。
第一行輸入兩個正整數n和k，代表城市的個數和Codancer現有的資金數目，接下來n-1行每行三個數u,v,w,代表城市u和城市v之間有一條長度為w的道路。（1<=n<=100000,1<=k<=1000,1<=u,v<=n,1<=w<=1000）
輸出codancer可選擇的方案數。
示例1
輸入：
3
[[1,2,1],[2,3,1]]
輸出：
注意
Codancer可以選擇從:
1->2
1->3
2->3
解題方法一
根據樣例資料 從1到2的花費為1，從1到3的花費為2，從2到3的花費為1，花費都小于3，是以總共有三種方案。
首先按照邊權将這些邊從小到大排序，使用并查集記錄目前連通塊内的最大的邊權。
當u和v連接配接起來的時候，假設此時的聯通塊大小為cnt,則答案應該加上cnt*(cnt-1)/2，同時應該減去之前u和v單獨為連通塊的方案數。
令ans[i]為最大邊權為第i條時構成的連通塊的方案數，那麼對于k，二分查找最大的小于等于k的下标id，最終答案就是ans[id]。
時間複雜度為：O(nlog(n))
解題方法二
雖然題中給出的是一個樹形結構，但是解題時和樹的關系不是很大。
題中指出從城市A到B的路費是從A-B的路徑上邊權最大的邊的權值wmaxx元。可以了解成對于權值大于現有資金數目k的邊，codancer不能通過，其他邊可以任意通過。是以原始的樹形結構被不能通過的邊分割成了多個子區域。每個子區域沒的任意兩個城市是可以互相到達的。每個子區域内方案數為C(n, 2)，n為子區域内城市個數。
對于子區域的計算可以考慮從底向上合并的形式。建立一個1*n的數組a，數組的每個位置代表一個城市，每個位置的内容代表這個城市所在的子區域。初始化時a[i] = i。周遊時，選擇可以通過的邊，把兩個邊對應的城市所屬子區域合并（修改成同樣的數字）即可。
時間複雜度O(2n) 第一遍判斷每個城市屬于哪個子區域。第二遍計算每個子區域城市個數，并用C(n, 2)求和。
空間複雜度O(n)
看完之後是不是有了答題思路了呢，快來練練手吧：
123.Codancer的旅行