CF1394D Boboniu and Jianghu

Since Boboniu finished building his Jianghu, he has been doing Kungfu on these mountains every day. Boboniu designs a map for his $ n $ mountains. He uses $ n-1 $ roads to connect all $ n $ mountains. Every pair of mountains is connected via roads. For the $ i $ -th mountain, Boboniu estimated the tiredness of doing Kungfu on the top of it as $ t_i $ . He also estimated the height of each mountain as $ h_i $ . A path is a sequence of mountains $ M $ such that for each $ i $ ( $ 1 \le i < |M| $ ), there exists a road between $ M_i $ and $ M_{i+1} $ . Boboniu would regard the path as a challenge if for each $ i $ ( $ 1\le i

N/A

N/A

For the first example: In the picture, the lighter a point is, the higher the mountain it represents. One of the best divisions is: - Challenge $ 1 $ : $ 3 \to 1 \to 2 $ - Challenge $ 2 $ : $ 5 \to 2 \to 4 $ The total tiredness of Boboniu is $ (30 + 40 + 10) + (20 + 10 + 50) = 160 $ . It can be shown that this is the minimum total tiredness.