题目描述

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$ 次道路建设的成本。

5
1 2 3 4 5
1 2
2 3
2 4
3 5

0
0
0
2

10
1 7 3 4 8 6 2 9 10 5
1 2
1 3
2 4
3 5
2 6
3 7
4 8
5 9
6 10

0
0
0
1
1
0
1
2
3

提示

样例 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 完成