← 返回题目列表

Codeforces · 1019/E

E. 雨季

中文机器翻译题面 查看原题

到了3018年,暑期信息学学校已经有了很大的发展。 «Berendeetronik» 酒店已被选为学校所在地。该营地由 $$$n$$$ 房屋组成,房屋之间有 $$$n-1$$$ 通道。通过这些路径可以到达每栋房屋。

一切都很完美,直到下雨。天气预报预计降雨将持续 $$$m$$$ 天。 A special squad of teachers was able to measure that the $$$i$$$-th pathway, connecting houses $$$u_i$$$ and $$$v_i$$$, before the rain could be passed in $$$b_i$$$ seconds.不幸的是,雨水侵蚀了道路,因此每天通过道路的时间都会增加 $$$a_i$$$ 秒。换句话说,在开始下雨后的第 $$$t$$$ 天(从零开始),需要 $$$a_i \cdot t + b_i$$$ 秒才能通过这条路。

Unfortunately, despite all the efforts of teachers, even in the year 3018 not all the students are in their houses by midnight.由于到了午夜所有学生都必须上床睡觉,因此找到每天所有对房屋之间的最大时间很重要,这样每个学生都会知道他必须跑到自己家的时间。

找出 $$$t=0$$$, $$$t=1$$$, ..., $$$t=m-1$$$ 天后每对房屋之间路径的最大次数。

输入

在第一行中,您将获得两个整数 $$$n$$$ 和 $$$m$$$ - 营地中的房屋数量和下雨天数($$$1 \le n \le 100\,000$$$; $$$1 \le m \le 1\,000\,000$$$)。

在接下来的 $$$n-1$$$ 行中,您将获得整数 $$$u_i$$$、$$$v_i$$$、$$$a_i$$$、$$$b_i$$$ - 路径描述 ($$$1 \le u_i, v_i \le n$$$; $$$0 \le a_i \le 10^5$$$; $$$0 \le b_i \le 10^9$$$)。 $$$i$$$-th 路径连接房屋 $$$u_i$$$ 和 $$$v_i$$$,并且在 $$$t$$$ 日需要 $$$a_i \cdot t + b_i$$$ 秒才能通过。

保证每两栋房子都通过一系列路径连接。

输出

打印 $$$m$$$ 整数 — 降雨开始后 $$$t=0, t=1, \ldots, t=m-1$$$ 天后营地中最长路径的长度。

示例

输入 #1

5 10
1 2 0 100
1 3 0 100
1 4 10 80
1 5 20 0

输出 #1

200 200 200 210 220 230 260 290 320 350

注意

让我们考虑第一个例子。

In the first three days ($$$0 \le t \le 2$$$) the longest path is between 2nd and 3rd houses, and its length is equal to $$$100+100=200$$$ seconds.

第三天 ($$$t=2$$$) 1 号房屋和 4 号房屋之间的道路长度为 $$$100$$$ 并且不断增加。因此,在 $$$t=2, 3, 4, 5$$$ 天内,最长路径位于顶点 4 和(1 或 2)之间,长度为 $$$180+10t$$$。请注意,在 $$$t=2$$$ 这一天,有 3 条长度为 100 的路径,因此存在 3 条长度相等的最大路径。

在第六天($$$t=5$$$),第一和第五个房子之间的路径长度为 100。因此,每天 $$$t=5$$$ 并且最长的路径位于 4 号和 5 号房子之间,长度为 $$$80+30t$$$。