Informatica Online Judge

  과수원1 [1264 / 04F0]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 11   Total Tried : 29


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

[JKJeong 2015]

Background

경곽이네 과수원에는 n그루의 과일나무가 있다.

각 과일 나무들은 양 방향으로 통행가능한 길로 연결되어 있다.

각 나무들을 연결하는 길은 n-1개가 있으며 임의의 과일 나무에서 길을 통하여 다른 과일나무로의 경로가 항상 존재한다.

경곽이는 올해 각 과일들을 수확하여 팔았을 때 얻는 가치를 알고 있다.

가치는 음의 값을 가질 수도 있다. 즉, 그 나무에서 과일을 따는데 비용이 팔아서 얻는 비용보다 적을 수 있다.

경곽이는 임의의 한 과일나무로부터 다른 과일나무까지를 연결하는 한 경로에 있는 모든 과일을 수확하고자 한다.

그런데 중간에 손해를 보는 과일 들 때문에 이득이 적어지는 것이 마음에 걸려 다음과 같이 수확하기로 했다.

- 임의의 두 과일나무 a, b를 정한다. (나무 a, b가 같을 수 있다.)
- 이 두 과일 나무 사이의 경로상에 존재하는 모든 과일, 즉 경로 상의 구간 [a, b]의 모든 과일을 수확한다.


각 과일나무 n개에 대해서 얻을 수 있는 이득과, 각 나무들을 연결하는 길 n-1개에 대한 정보가 주어질 때,

위 조건을 만족하도록 수확할 때 얻을 수 있는 최대이익을 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 과일나무의 수를 나타내는 정수 n이 입력된다.

두 번째 줄에 n개의 나무의 가치를 나타내는 정수 w_i개 공백으로 구분되어 입력된다.

다음 줄부터 n-1개의 줄에 걸쳐서 각 나무들을 연결하는 길의 정보가 공백으로 구분되어 입력된다.

[입력값의 정의역]
1 <= n <= 100,000
-1,000 <= w_i <= 1,000

Output

수확하여 얻을 수 있는 최대 이익을 출력한다.

IO Example

입력
5
3 2 -1 3 4
1 2
2 3
3 4
4 5


출력
11

*해설
(3) - (2) - (-1) - (3) - (4) 의 형태로 구성된 과수원이다.
가장 왼쪽의 과일나무로부터 가장 오른쪽까지 모든 구간의 과일을 수확하는 것이 11로 가장 이득이다.

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