遇到一个选方案问题，求解答
期末考试终于结束啦，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 可选择的方案数。
写回答
-
虽然题中给出的是一个树形结构，但是解题时和树的关系不是很大。题中指出从城市 A 到 B 的路费是从 A-B 的路径上边权最大的边的权值 wmaxx元。可以理解成对于权值大于现有资金数目 k 的边，codancer 不能通过，其他边可以任意通过。所以原始的树形结构被不能通过的边分割成了多个子区域。每个子区域没的任意两个城市是可以互相到达的。每个子区域内方案数为 C(n, 2)，n 为子区域内城市个数。对于子区域的计算可以考虑从底向上合并的形式。创建一个1*n的数组a，数组的每个位置代表一个城市，每个位置的内容代表这个城市所在的子区域。初始化时a[i] = i。遍历时，选择可以通过的边，把两个边对应的城市所属子区域合并（修改成同样的数字）即可。时间复杂度 O(2n) 第一遍判断每个城市属于哪个子区域。第二遍计算每个子区域城市个数，并用 C(n, 2) 求和。空间复杂度 O(n) 因此输入：3 3 [[1,2,1],[2,3,1]] 输出：3 注：Codancer 可以选择从 : 1->2 1->3 2->3
2021-12-23 18:50:36赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
