CF1019E Raining season

到了 3018 年，夏季信息学学校已经大大扩展。学校选址在酒店「Berendeetronik」。营地由 $n$ 栋房屋和 $n-1$ 条小路组成。通过这些小路，可以从任意一栋房屋到达其他所有房屋。 一切本来都很完美，直到下雨季节来临。天气预报称，雨季将持续 $m$ 天。教师特别小队测量得知，第 $i$ 条小路连接房屋 $u_i$ 和 $v_i$，在下雨前通过这条小路需要 $b_i$ 秒。不幸的是，雨水会侵蚀道路，因此每过一天，经过这条小路所需的时间会增加 $a_i$ 秒。换句话说，在下雨开始后的第 $t$ 天（从零开始计），通过这条小路需要 $a_i \cdot t + b_i$ 秒。 遗憾的是，即使到了 3018 年，仍然有学生在午夜时分还未回到自己的房间。由于所有学生必须在午夜前回到房间，因此需要计算每天所有房屋对之间的最长路径长度，这样每个学生都能知道自己最晚需要多长时间才能回到房间。 请你计算 $t=0,1,\ldots,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$ 条小路连接房屋 $u_i$ 和 $v_i$，在第 $t$ 天通过这条小路需要 $a_i \cdot t + b_i$ 秒。 保证任意两栋房屋之间都可以通过若干条小路连通。

输出 $m$ 个整数，第 $i$ 个整数表示下雨开始后第 $t=i-1$ 天时，营地中所有房屋对之间的最长路径长度。

我们来看第一个样例。 在前三天（$0 \le t \le 2$）最长路径是第 2 号房屋到第 3 号房屋，长度为 $100+100=200$ 秒。 在第 3 天（$t=2$）时，1 号和 4 号房屋之间的小路长度变为 $100$，并且还在增加。因此，在第 $t=2,3,4,5$ 天，最长路径是 4 号房屋到（1 号或 2 号房屋），长度为 $180+10t$。注意，在 $t=2$ 天时，有三条长度为 100 的小路，因此有三条最长路径长度相同。 在第 6 天（$t=5$）时，1 号和 5 号房屋之间的小路长度变为 100。因此，从 $t=5$ 天及以后，最长路径是 4 号房屋到 5 号房屋，长度为 $80+30t$。 由 ChatGPT 4.1 翻译