页面无法加载？点击这里可能会修复。
Placeholder

#8233
子任务

도로 건설 1s 256MB

问题

JOI 왕국에는 N개의 도시가 있고, 이 도시는 1부터 N까지 번호가 매겨져 있다. 도시 1은 수도이다. 각 도시는 활기라는 값을 가지며, 도시 i(1 ≤ i ≤ N)의 초기 활기 값은 C_i이다.

JOI 왕국에서는 두 도시를 양방향으로 연결하는 도로를 건설할 수 있다. 처음에는 도로가 없다. N - 1개의 도로 건설 계획이 있다. j번째 도로 건설(1 ≤ j ≤ 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로 가는 도중 s에 먼저 도착한 후 t에 도착한다.

    • 도시 s의 활기 값이 도시 t의 활기 값보다 크다.

  3. 도시 1에서 도시 A_j까지 최단 경로 상의 모든 도시의 활기 값이 도시 B_j의 활기 값으로 변경된다.

각 도로 건설의 비용을 구하는 프로그램을 작성하라.


输入

다음 데이터가 표준 입력으로 주어진다.

  • 첫 번째 줄에 정수 N이 주어진다. 이는 JOI 왕국에 N개의 도시가 있다는 뜻이다.

  • 두 번째 줄에 C_1, C_2, \cdots, C_N이 공백으로 구분되어 주어진다. 이는 도시 i(1 ≤ i ≤ N)의 초기 활기 값을 나타낸다.

  • 다음 N − 1개의 줄의 j번째 줄(1 ≤ j ≤ N − 1)에 두 정수 A_j, B_j가 공백으로 구분되어 주어진다. 이는 도시 A_j와 B_j가 j번째 도로 건설에서 지정되었음을 의미한다.

제한

  • 1 ≤ N ≤ 100,000

  • 1 ≤C_i≤ 1,000,000,000 (1 ≤ i ≤ N)

  • 1 ≤ A_j ≤ N (1 ≤ j ≤ N − 1)

  • 1 ≤ B_j ≤ N (1 ≤ j ≤ N − 1)

  • j번째 도로 건설 이전에, 도시 1에서 도시 A_j로 갈 수 있고 도시 B_j로는 갈 수 없다.


输出

N − 1개의 줄을 표준 출력으로 출력한다. j번째 줄(1 ≤ j ≤ N − 1)에는 j번째 도로 건설 비용을 출력한다.


子任务

编号 分数 条件
#17分

N ≤ 500

#29分

N ≤ 4000

#384分

추가 제한 조건 없음


示例 #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로 변경된다.

  2. 두 번째 도로 건설에서도 조건을 만족하는 쌍 (s, t)가 없으므로 비용은 0이다. 도시 2와 도시 3을 연결하는 도로가 건설되고, 도시 1과 도시 2의 활기 값이 3으로 변경된다.

  3. 세 번째 도로 건설에서도 조건을 만족하는 쌍 (s, t)가 없으므로 비용은 0이다. 도시 2와 도시 4를 연결하는 도로가 건설되고, 도시 1과 도시 2의 활기 값이 4로 변경된다.

  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

来源

JOI 2017/2018 Spring Training Camp
需要登录才能编写代码。