高速公路建设 - Problem

JOI 王国共有 $N$ 座城市，编号为 $1$ 到 $N$。城市 $1$ 是首都。每座城市都有一个称为“活跃度”的数值，城市 $i$ ($1 \le i \le N$) 的初始活跃度为 $C_i$。

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, \dots, C_N$。这意味着城市 $i$ ($1 \le i \le N$) 的初始活跃度为 $C_i$。
接下来的 $N-1$ 行中的第 $j$ 行 ($1 \le j \le N-1$) 包含两个空格分隔的整数 $A_j, B_j$。这意味着城市 $A_j$ 和城市 $B_j$ 被指定用于第 $j$ 次道路建设。

输出 $N-1$ 行到标准输出。第 $j$ 行 ($1 \le j \le N-1$) 包含第 $j$ 次道路建设的成本。

所有输入数据满足以下条件：

$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 中，建设过程如下：

第一次建设时，没有满足条件的城市对 $(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$。

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

QOJ.ac