题目描述

题目译自 CEOI 2024 Day2 T2「Petrol stations」

捷克的高速公路网络由 $N$ 个城市和 $N-1$ 条路组成，每条路的长度（公里）已知。我们知道任意两个城市之间只有一条路径。此外，每个城市恰好有一个加油站，其他地方没有。

有一天，许多人决定开车旅行。总共有 $N^2$ 辆车在路上。奇怪的是，对于每个有序城市对 $(a, b)$，恰好有一辆车从城市 $a$ 开往城市 $b$，沿着这两个城市之间唯一的路径行驶。由于捷克人全都开斯柯达车，每辆车的油箱容量都是 $K$ 升，并且每公里消耗一升汽油。出发前，每辆车的油箱都是满的。此外，捷克人非常有规律。由于懒惰，他们只在汽油不足以到达下一个城市时才加油（油箱为空时可以进入城市）。一旦他们被迫停在加油站，他们总是把油箱加满。

捷克税务部门想知道当天每个加油站停了多少辆车。鉴于这种可预测的行为，你应该能够轻松计算出来。

输入格式

输入的第一行包含两个空格分隔的整数 $N$ 和 $K$，分别表示城市数量和每辆车的油箱容量。

接下来的 $N-1$ 行描述道路。每行包含三个空格分隔的整数 $u_i, v_i, l_i$，其中 $u_i$ 和 $v_i$ 是第 $i$ 条路连接的城市编号，$l_i$ 是这条路的长度（公里）。城市从 $0$ 到 $N-1$ 编号。保证任意两个城市之间只有一条路径。

输出格式

输出 $N$ 行，表示从城市 $0$ 到城市 $N-1$ 每个城市加油站停靠的汽车数。

3 1
0 1 1
1 2 1

0
2
0

6 2
0 1 1
1 2 1
2 3 1
3 4 2
4 5 1

0
3
3
12
8
0

提示

样例解释 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$ 表示连接到单个城市的道路的最大数量。详细子任务附加限制及分值如下表所示。