Informatica Online Judge

  편의점 [1407 / 057F]

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


The Champion of this Problem (C++) : gs18070 - 0ms / 1118byte
My Best Submission (C++) : N/A

[]

Background

국내 굴지의 A 편의점은 X 나라로 사업을 진출하려고 한다. X 나라는 어떤 마을과 마을 사이에 정확히 하나의 경로만 있다.

그런데 X 나라는 해외에서 과도하게 매장을 오픈하는 것을 방지하고자 다음과 같은 규약을 정하였다.

- 인접한 마을끼리 동일한 매장 오픈은 할 수 없다.

X 나라가 사업체에게 제공해주는 것은 마을과 마을사이의 연결 도로, 마을의 거주인원수이다. 편의점이 최대의 소비자를 확보하도록 매장을 설치하면 몇 명이나 되는지 프로그램을 작성하시오.



예를 들어, 3개의 마을(1,2,3)과 각 거주인원(10, 20, 25) 이 있을 때 1번 마을과 2번 마을에 편의점을 설치해야 30명의 소비자를 확보할 수 있게 된다.

Input

첫 번째 줄에는 전체 마을 수(1<=N<=100,000)를 입력한다.

두 번째 줄 부터는 각 마을 별 거주인원을 입력한다. 거주인원은 첫 번째 마을(1)부터 N번째 마을(N)까지 순서대로 입력한다 (1, 2, 3,....N).

마을 거주인원 입력이 끝나면, 연결이 된 마을과 마을의 번호를 입력한다. 각 마을은 최대 50개의 마을과 연결될 수 있다.

Output

편의점을 설치해서 확보할 수 있는 최대 소비자수를 출력한다.

IO Example

입력1
3
10
20
25
1 3
2 3

출력1
30

입력2
6
10
20
22
40
30
30
6 4
4 5
1 3
2 3
3 4

출력2
90

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