n1 springs to connect them into a tree.1 is the root of the tree. Now we grasp the root and hang the whole tree.At this time, PaiGuDragon come up with an evil idea. It plans to rearrange the. w sequence, that is, PaiGuDragon is going to generate an array. Considering all the arrangements, what is the maximum of maximum depth of the tree after hanging?Here, the maximum depth is defined as the maximum value of the sum of the spring lengths on the path from the leaf to the root.
There are n n iron balls numbered 1 1 to n n, and the weight of the i i th ball is w_i w i . We use n - 1 n−1 springs to connect them into a tree. The ball numbered 1 1 is the root of the tree. Now we grasp the root and hang the whole tree. The initial length of each spring is 1 1. If the weight of the subtree it hangs is g g, its length will become 1 + g 1+g. At this time, PaiGuDragon come up with an evil idea. It plans to rearrange the w w sequence, that is, PaiGuDragon is going to generate an array p_1,p_2,...,p_n p 1 ,p 2 ,...,p n which is a permutation of 1,2....,n 1,2....,n, and then the weight of the i i th ball will become w_{p_i} w p i Considering all the arrangements, what is the maximum of maximum depth of the tree after hanging? Here, the maximum depth is defined as the maximum value of the sum of the spring lengths on the path from the leaf to the root.
