NC53242. 道路建设

描述

输入描述

输入数据的第一行包含一个整数N，表示JOI王国有N座城市。
第二行包含N个以空格分开的整数，表示第座城市的初始活跃度是。
接下来N-1行中的第j行包含两个以空格分开的整数和，表示第j次道路建设所指定的两个端点编号分别为和。

输出描述

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

示例1

输入:

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

输出:

0
0
0
2

说明:

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

示例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

原站题解