#2831. 「JOISC 2018 Day 1」道路建设

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: fbhou

题目描述

译自 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

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

输出样例 1

0
0
0
2

样例说明 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

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

输出样例 2

0
0
0
1
1
0
1
2
3

数据范围与提示

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

  • 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 分)

没有额外限制。