CF1988D The Omnipotent Monster Killer

You, the monster killer, want to kill a group of monsters. The monsters are on a tree with $ n $ vertices. On vertex with number $ i $ ( $ 1\le i\le n $ ), there is a monster with $ a_i $ attack points. You want to battle with monsters for $ 10^{100} $ rounds. In each round, the following happens in order: 1. All living monsters attack you. Your health decreases by the sum of attack points of all living monsters. 2. You select some (possibly all or none) monsters and kill them. After being killed, the monster will not be able to do any attacks in the future. There is a restriction: in one round, you cannot kill two monsters that are directly connected by an edge. If you choose what monsters to attack optimally, what is the smallest health decrement you can have after all rounds?

N/A

N/A

In the first test case, an optimal sequence of operations would be: - In the first round: first, receive the attack from the monster on vertex $ 1 $ , so your health decreases by $ 10^{12} $ . Then kill the monster on vertex $ 1 $ . - In the second round to the $ 10^{100} $ -th round: all monsters have been killed, so nothing happens. The total health decrement is $ 10^{12} $ . In the second test case, an optimal sequence of operations would be: - In the first round: first, receive the attack from the monster on vertex $ 1,2,3,4,5 $ , so your health decreases by $ 47+15+32+29+23=146 $ . Then kill the monsters on vertex $ 1,4,5 $ . - In the second round: first, receive the attack from the monster on vertex $ 2,3 $ , so your health decreases by $ 15+32=47 $ . Then kill the monsters on vertex $ 2,3 $ . - In the third round to the $ 10^{100} $ -th round: all monsters have been killed, so nothing happens. The total health decrement is $ 193 $ . In the third test case, an optimal sequence of operations would be: - In the first round: first, receive the attack from the monster on vertex $ 1,2,3,4,5,6,7 $ , so your health decreases by $ 8+10+2+3+5+7+4=39 $ . Then kill the monsters on vertex $ 1,3,6,7 $ . - In the second round: first, receive the attack from the monster on vertex $ 2,4,5 $ , so your health decreases by $ 10+3+5=18 $ . Then kill the monsters on vertex $ 2,4,5 $ . - In the third round to the $ 10^{100} $ -th round: all monsters have been killed, so nothing happens. The total health decrement is $ 57 $ .