P14365 [JOISC 2018] 高速公路建设 / Construction of Highway

JOI 王国有 $N$ 个城市，编号从 $1$ 到 $N$。城市 $1$ 是首都。每个城市都有一个称为“活力值”的数值，城市 $i$（$1 \le i \le N$）的初始活力值为 $C_i$。 JOI 王国中的道路是双向连接两个不同城市的。最初，JOI 王国中没有道路。你计划进行 $N-1$ 次道路建设。第 $j$ 次建设（$1 \le j \le N-1$）按以下方式进行： - 选定两个城市 $A_j$ 和 $B_j$，满足：仅使用当时已建成的道路，可以从城市 $1$ 到达城市 $A_j$，但无法从城市 $1$ 到达城市 $B_j$。 - 你建设一条连接城市 $A_j$ 和城市 $B_j$ 的道路。此次建设的成本是满足以下条件的城市对 $(s, t)$ 的数量： 城市 $s$ 和城市 $t$ 位于从城市 $1$ 到城市 $A_j$ 的最短路径上，且当从城市 $1$ 前往城市 $A_j$ 时，先经过城市 $s$，再经过城市 $t$，且城市 $s$ 的活力值严格大于城市 $t$ 的活力值。 这里，位于城市 $1$ 和城市 $A_j$ 之间的路径上的城市包括城市 $1$ 和城市 $A_j$。注意，城市 $1$ 与城市 $A_j$ 之间的最短路径是唯一的。 - 所有位于城市 $1$ 与城市 $A_j$ 之间路径上的城市的活力值，均更新为城市 $B_j$ 的活力值。 你希望知道每次建设的成本。 **任务** 给定城市数据和道路建设方案，编写一个程序，计算每次建设的成本。

从标准输入读取以下数据： - 输入的第一行包含一个整数 $N$。这意味着 JOI 王国有 $N$ 个城市。 - 输入的第二行包含 $N$ 个以空格分隔的整数 $C_1, C_2, \cdots, C_N$。这意味着城市 $i$（$1 \le i \le N$）的初始活力值为 $C_i$。 - 接下来的 $N-1$ 行中，第 $j$ 行（$1 \le j \le N-1$）包含两个以空格分隔的整数 $A_j, B_j$。这意味着在第 $j$ 次道路建设中，选定城市 $A_j$ 和城市 $B_j$。

向标准输出写入 $N-1$ 行。第 $j$ 行（$1 \le j \le N-1$）包含第 $j$ 次道路建设的成本。

### 样例 1 解释 在样例输入 1 中，建设过程如下： - 在第一次建设中，不存在满足条件的城市对 $(s, t)$，因此成本为 $0$。修建一条连接城市 $1$ 和城市 $2$ 的道路，城市 $1$ 的活力值更新为 $2$。 - 在第二次建设中，同样不存在满足条件的城市对 $(s, t)$，因此成本为 $0$。修建一条连接城市 $2$ 和城市 $3$ 的道路，城市 $1$ 和城市 $2$ 的活力值均更新为 $3$。 - 在第三次建设中，仍不存在满足条件的城市对 $(s, t)$，因此成本为 $0$。修建一条连接城市 $2$ 和城市 $4$ 的道路，城市 $1$ 和城市 $2$ 的活力值均更新为 $4$。 - 在第四次建设中，有两个城市对 $(s, t) = (1,3), (2,3)$ 满足条件，因此成本为 $2$。修建一条连接城市 $3$ 和城市 $5$ 的道路，城市 $1$、城市 $2$ 和城市 $3$ 的活力值均更新为 $5$。 ### 数据范围 所有输入数据满足以下条件： - $1 \le N \le 100\,000$。 - $1 \le C_i \le 1\,000\,000\,000$（$1 \le i \le N$）。 - $1 \le A_j \le N$（$1 \le j \le N-1$）。 - $1 \le B_j \le N$（$1 \le j \le N-1$）。 - 在第 $j$ 次建设之前，仅使用已建成的道路，可以从城市 $1$ 到达城市 $A_j$，但无法从城市 $1$ 到达城市 $B_j$（$1 \le j \le N-1$）。 ### 子任务 共有 3 个子任务。每个子任务的得分和附加约束如下： **子任务 1 [7 分]** - $N \le 500$。 **子任务 2 [9 分]** - $N \le 4000$。 **子任务 3 [84 分]** 无额外约束。 翻译由 Qwen3-235B 完成