【在线编程产品介绍】

阿里云开发者社区在线编程：

免费刷题大神器，助你拿到好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
3
[[1,2,1],[2,3,1]]
输出：
3

注意
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的旅行