CF82C General Mobilization

伯兰王国有 $n$ 个城市，这些城市通过 $n-1$ 条铁路相连。每条铁路正好连接两座不同的城市。首都位于城市 $1$。对于每个城市，都存在一条由铁路到达首都的路径。 第 $i$ 个城市驻扎着编号为 $i$ 的部队，该部队有一个优先级 $a_{i}$。优先级数值越小，优先级越高。所有 $a_{i}$ 的数值互不相同。 有一天，伯兰国王 Berl Great 宣布全民动员，每支部队都必须赶到首都。每天，除了首都以外的每座城市都会发出一列火车。因此，每天将有 $n-1$ 列火车发车。每列火车朝首都方向前进，并在第二天到达这条铁路的另一端。每列火车有一个有限的运力 $c_{j}$，这代表该列火车一次最多可以运送的部队数量。每列火车都会沿着距离首都更近的方向出发，每次穿越一条铁路，从一个城市移动到相邻的另一个城市（并在此停下）。 在每个城市中，优先级最小（$a_{i}$ 最小）的部队优先上车，然后是下一个小的，直到火车满员或所有部队都已登车。因此，一支部队可能会在某个城市停留多天。 火车从一个城市到另一个城市的运行时间始终为 $1$ 天。所有部队同时出发，最终汇集于首都，并不再离开。每支部队会沿着从自己城市到首都的最短简单路径前进，无论到达路程需要多少天。 你的任务是求出每支部队从出发地前往首都需要多少天。计时从第 $0$ 天开始。

第一行包含一个整数 $n$（$1\leq n\leq 5000$），表示伯兰的城市数量。 第二行包含 $n$ 个用空格分隔的整数 $a_{1},a_{2},...,a_{n}$，其中 $a_{i}$ 表示分布在第 $i$ 个城市的部队优先级。所有 $a_{i}$ 互不相同（$1\leq a_{i}\leq 10^{9}$）。 接下来的 $n-1$ 行，每行包含三个整数 $v_{j},u_{j},c_{j}$，$v_{j}$ 和 $u_{j}$ 表示第 $j$ 条铁路连接的两个城市编号，$c_{j}$ 表示该铁路最大运力（$1\leq v_{j},u_{j}\leq n$，$v_{j}\neq u_{j}$，$1\leq c_{j}\leq n$）。

输出一个长度为 $n$ 的序列 $t_{1}, t_{2}, \ldots, t_{n}$，其中 $t_{i}$ 表示第 $i$ 个城市的部队到达首都所需的天数。用空格分隔。

由 ChatGPT 5 翻译