「JOISC 2018 Day 1」道路建设 - Problem - HelloWorld信息学奥赛题库

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}$ 时，他会在经过 $t$ 之前经过 $s$；
- $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$ 行包含两个以空格分开的整数 $A{j}$ 和 $B{j}$，表示第 $j$ 次道路建设所指定的两个端点编号分别为 $A{j}$ 和 $B{j}$。

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

input

output

在输入样例 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$。

input

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

output

全部的输入数据满足以下条件：

$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}$。

$N\le 500$。

$N\le 4000$。

没有额外限制。

HelloWorld信息学奥赛题库