Sjekira
레이팅 미적용의견: 0
Mirko is tired of his stressful CEO job in a we\(ll-kn\)own multinational software
company. With a golden parachute of several million dollars, he decided to live
a simple life and move to Gorski Kotar. However, winters in the remote village
he just moved in are tough. None of his neighbours were born after WWII, so he
is destined to chop firewood himself.
Today, he is going to chop his first trunk. Before chopping, he labels the parts of
the trunk which are small enough to fit in a fireplace, and measures their hardness.
Mirko is a programmer, so he notices that the parts and the connections between
them form a tree graph.
The damage on his axe resulting from cutting a connection on the trunk is equal to the sum of the
maximal hardnesses in the two connected components formed by cutting the connection.
Mirko has only one axe, so he wants the total damage to be as small as possible. He wants to know the
minimal total damage on the axe, if he cuts the whole trunk into single parts which fit in a fireplace.
Subtask 1 (10 points): \(1 \le n \le 10\)
Subtask 2 (10 points): Parts \(i\) and \(i + 1\) (\(1 \le i \le n - 1\)) are directly connected.
Subtask 3 (30 points): \(1 \le n \le 1000\)
Subtask 4 (60 points): \(1 \le n \le 100\,000\)
The first line contains an integer \(n\), the number of parts. The parts are labeled by integers from 1 to \(n\).
The second line contains \(n\) integers \(t@@RISE_MATH_BLOCK_0@@i \le 10^{9}\)). The number \(t\)\(i\) is the hardness of the part labeled \(i\).
Each of the following \(n - 1\) lines contains two integers \(x\) and \(y\) (\(1 \le x\), \(y \le n\)) – labels of parts that are
directly connected.
Output the minimal total damage after \(n - 1\) cuts.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 10점 | \(1 \le n \le 10\) |
2 | 10점 | Parts \(i\) and \(i + 1\) (\(1 \le i \le n - 1\)) are directly connected. |
3 | 30점 | \(1 \le n \le 1000\) |
4 | 60점 | \(1 \le n \le 100\,000\) |
3
1 2 3
1 2
2 384
2 2 3 2
1 3
3 2
4 3155
5 2 3 1 4
2 1
3 1
2 4
2 526Clarification of the first example:
There are two ways to cut this trunk. He can first cut the connection (1, 2), which causes 1 + 3 = 4
damage, and then cut the connection (2, 3), which causes 2 + 3 = 5 damage. The total damage is 9 in this
case.
Otherwise, he can first cut (2, 3), and then (1, 2). The total damage in that case (2 + 3) + (1 + 2) = 8.
평가 및 의견
Sjekira
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Sjekira