2831 「JOISC 2018 Day 1」道路建设

译自 JOISC 2018 Day1 T1「高速道路の建設 / 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)$ 个项目会按以下方式完成：

1. 指定两座城市 $A_{j}$ 和 $B_{j}$，要求能沿着此时已经建设的道路从城市 $1$ 走到城市 $A_{j}$，且不能从城市 $1$ 走到城市 $B_{j}$。
2. 建设一条连接城市 $A_{j}$ 和 $B_{j}$ 的道路。建设过程的费用等于满足以下条件的城市对 $(s,t)$ 的个数：
   • $s$ 和 $t$ 在从城市 $1$ 到城市 $A_{j}$ 的最短路径上；
   • 当一个人从城市 $1$ 走到 $A_{j}$ 时，他会在经过 $t$ 之前经过 $s$；
   • $s$ 的活跃度严格大于 $t$ 的活跃度。
     在这里，「从城市 $1$ 到城市 $A_{j}$ 的最短路径上的城市」包括 $1$ 和 $A_{j}$ 。注意从城市 $1$ 到城市 $A_{j}$ 的最短路径是唯一的。
3. 将从城市 $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$ 行包含两个以空格分开的整数 $A_{j}$ 和 $B_{j}$，表示第 $j$ 次道路建设所指定的两个端点编号分别为 $A_{j}$ 和 $B_{j}$。

输出到标准输出，共 $N-1$ 行，第 $j(1\le j\le N-1)$ 行包含一个整数表示第 $j$ 次道路建设的费用。

在输入样例 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 100000$
• $1\le C_{i}\le 10^{9} (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\le j\le N-1)$ 次建设，能沿着此时已经建设的道路从城市 $1$ 走到城市 $A_{j}$，且不能从城市 $1$ 走到城市 $B_{j}$。

子任务 1（7 分）

$N\le 500$。

子任务 2（9 分）

$N\le 4000$。

子任务 3（84 分）

没有额外限制。