[CEOI 2024] 加油站

**题目译自 [CEOI 2024](https://ceoi2024.fi.muni.cz/) Day2 T2「[Petrol stations](https://ceoi2024.fi.muni.cz/page/tasks/statements/stations.pdf)」** 捷克的高速公路网络由 $N$ 个城市和 $N-1$ 条路组成，每条路的长度（公里）已知。我们知道任意两个城市之间只有一条路径。此外，每个城市恰好有一个加油站，其他地方没有。 有一天，许多人决定开车旅行。总共有 $N^2$ 辆车在路上。奇怪的是，对于每个有序城市对 $(a, b)$，恰好有一辆车从城市 $a$ 开往城市 $b$，沿着这两个城市之间唯一的路径行驶。由于捷克人全都开斯柯达车，每辆车的油箱容量都是 $K$ 升，并且每公里消耗一升汽油。出发前，每辆车的油箱都是满的。此外，捷克人非常有规律。由于懒惰，他们只在汽油不足以到达下一个城市时才加油（油箱为空时可以进入城市）。一旦他们被迫停在加油站，他们总是把油箱加满。 捷克税务部门想知道当天每个加油站停了多少辆车。鉴于这种可预测的行为，你应该能够轻松计算出来。 ## Input 输入的第一行包含两个空格分隔的整数 $N$ 和 $K$，分别表示城市数量和每辆车的油箱容量。 接下来的 $N-1$ 行描述道路。每行包含三个空格分隔的整数 $u_i, v_i, l_i$，其中 $u_i$ 和 $v_i$ 是第 $i$ 条路连接的城市编号，$l_i$ 是这条路的长度（公里）。城市从 $0$ 到 $N-1$ 编号。保证任意两个城市之间只有一条路径。 ## Output 输出 $N$ 行，表示从城市 $0$ 到城市 $N-1$ 每个城市加油站停靠的汽车数。 [samples] ## Note **样例解释 1** 有 $3$ 座城市呈直线排列，连接它们的道路长度为 $1$，油箱容量为 $1$ 升。只有在两个外围城市之间行驶的汽车会在中间城市加油。 **样例解释 2** 有 $6$ 个城市呈直线排列，油箱容量为 $2$ 升。许多汽车需要在城市 $3$ 和城市 $4$ 加油。这是有道理的，因为城市 $3$ 和城市 $4$ 之间的道路长度为 $2$ 公里。 对于所有输入数据，满足： - $2 \leq N \leq 70\,000$ - $1 \leq K \leq 10^9$ - $0 \leq l_i \leq K\ (0 \leq i \leq N-2)$ 令 $D$ 表示连接到单个城市的道路的最大数量。详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :--: | :--: | :--: | | $1$ | $N \leq 1\,000, K \leq 1\,000$ | $18$ | | $2$ | $D\le 2$ 且 $l_i = 1\ (0 \leq i \leq N-2)$ | $8$ | | $3$ | $D\le 2$| $10$ | | $4$ | $K\leq 10, D\leq 10$ | $12$ | | $5$ | $K\leq 10$ | $17$ | | $6$ | 无附加限制| $35$ |