Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

bzoj 3784: 树上的路径

题目链接

传送门

Description

给定一个N个结点的树,结点用正整数1..N编号。每条边有一个正整数权值。用d(a,b)表示从结点a到结点b路边上经过边的权值。其中要求a<b.将这n*(n-1)/2个距离从大到小排序,输出前M个距离值。

Input

第一行两个正整数N,M
下面N-1行,每行三个正整数a,b,c(a,b<=N,C<=10000)。表示结点a到结点b有一条权值为c的边。

Output

共M行,如题所述.

Sample Input

5 10

1 2 1

1 3 2

2 4 3

2 5 4

Sample Output

7

7

6

5

4

4

3

3

2

1

题解

这题用到了点分治的思想
但是重点是统计答案
首先在点分治中,我们每个点最多会被遍历logn次,那么我们可以每次点分治的时候将点按照遍历的顺序加入队列,我们每次加入的是以某个节点为起点的路径,那么所有的路径都可以由两条相交于一点(除该点没有交集)的路径构成。
那么也就是对于我们加入队列的路径,能跟他配对的路径会是两段区间。
那么我们可以参考超级钢琴的思路去统计答案。
有关超级钢琴大概在这里 传送门

代码

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏