首页 > 试题广场 >

直径

[编程题]直径
给你N个点的树，每条边都有权重。
定义树上两个点的距离为此两点所形成的路径的权重和。
N个点能形成N(N-1)/2组点对，把这些点对的距离由大到小排序后，请输出前K大的距离数值。(若多组相异点对距离相同，该距离就要算不止一次)

输入描述:
数据共有N行。
第一行包含两个正整数N,K，分别代表树的点数以及要输出前几大的点对距离。
接下来的N-1行每行个包含三个整数x,y,v代表此树中，点x和点y之间有一条权重为v的边。


输出描述:
请输出K行，每行各包含一个正整数，第i行的数字代表第i大的点对距离。
示例1

输入

4 6
0 1 1
0 2 2
0 3 4

输出

6
5
4
3
2
1
示例2

输入

7 20
0 1 3
0 2 2
1 3 11
1 4 5
2 5 23
2 6 7

输出

39
33
30
28
25
23
23
17
16
16
14
12
11
10
9
8
7
5
5
3

备注:
2<=N<=2*105
1<=K<=N(N-1)/2
2<=N*K<=2*107
0<=x,y
1<=v<=109
题目给的图是一个树(tree)
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

堆/优先队列 搜索减枝
上传者：牛客301599号
难度：
0条回答 20浏览

热门推荐

通过挑战的用户

查看代码

相关试题

直径

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号