Informatica Online Judge

  건물 오르기 #2 [2372 / 0944]

Time Limit(Test case) : 1500(ms)
Number of users who solved : 12   Total Tried : 13


The Champion of this Problem (C++) : gs17074 - ms / 1039byte
My Best Submission (C++) : N/A

[36th 최은수(gs18115)]
Writer ID : [gs18115]

Background

명진이는 탁구를 좋아한다.
명진이는 운동을 하여 탁구 실력을 기르려고 한다.
명진이는 경곽에 살고 있다.
경곽에는 N개의 건물이 있고, N-1개의 도로로 모든 건물이 이어져 있다.
N개의 건물에는 높이가 있는데, 경곽은 이상한 도시라서 높이가 음수인 건물이 있다. 높이가 음수인 건물은 시간이 거꾸로 흐르기 때문에, 그 건물을 오르면 운동을 하는 역효과가 나게 된다.
명진이는 매일 새로운 경로 하나를 택해서, 그 경로에 있는 건물 중 하나를 오르고, 그 건물의 높이만큼의 운동을 한다.
그러나 명진이는 귀찮기 때문에, 가장 낮은 건물을 오른다.
만약 택할 새로운 경로가 없다면, 운동을 종료한다.
명진이가 운동을 끝낼 때까지 할 수 있는 총 운동의 양을 구해 주자!

Input

첫 번째 줄에 경곽에 있는 건물의 개수 N이 주어진다. (N <= 200,000)
다음 줄에는 N개의 수가 주어지고, i번째 수는 건물 i의 높이인 h_i를 의미한다. (-10^8 <= h_i <= 10^8)
3번째 줄부터 N+1번째 줄까지는 각 도로의 정보가 주어진다.

[Subtask Info]
Subtask #1 : N<=2,000
Subtask #2 : 입력으로 주어지는 트리는 1을 루트로 하는 완전 이진 트리이다.
Subtask #3 : 추가적인 제한조건이 없다.

Output

모든 경로에 대해 명진이가 운동하는 양의 합을 출력한다.
(한 정점만을 포함하는 경로도 경로라고 생각한다.)

IO Example

입력1
3
1 2 2
1 2
1 3

출력1
8

입력2
6
10 4 2 8 7 3
1 2
1 3
1 4
2 5
2 6

출력2
84

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]