문제
JOI 왕국에는 N개의 도시가 있고, 이 도시는 1부터 N까지 번호가 매겨져 있다. 도시 1은 수도이다. 각 도시는 활기라는 값을 가지며, 도시 i(1 ≤ i ≤ N)의 초기 활기 값은
JOI 왕국에서는 두 도시를 양방향으로 연결하는 도로를 건설할 수 있다. 처음에는 도로가 없다. N - 1개의 도로 건설 계획이 있다. j번째 도로 건설(1 ≤ j ≤ 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 로 가는 도중s 에 먼저 도착한 후t 에 도착한다.도시
s 의 활기 값이 도시t 의 활기 값보다 크다.
도시 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번째 도로 건설 비용을 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 7점 | |
| #2 | 9점 | |
| #3 | 84점 | 추가 제한 조건 없음 |
예제 #1
5
1 2 3 4 5
1 2
2 3
2 4
3 5
0
0
0
2
첫 번째 도로 건설에서는 조건을 만족하는 쌍
(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
로그인해야 코드를 작성할 수 있어요.