CF1088E Ehab and a component choosing problem

You're given a tree consisting of $ n $ nodes. Every node $ u $ has a weight $ a_u $ . You want to choose an integer $ k $ $ (1 \le k \le n) $ and then choose $ k $ connected components of nodes that don't overlap (i.e every node is in at most 1 component). Let the set of nodes you chose be $ s $ . You want to maximize: $ $$$\frac{\sum\limits_{u \in s} a_u}{k} $ $

In other words, you want to maximize the sum of weights of nodes in $ s $ divided by the number of connected components you chose. Also, if there are several solutions, you want to maximize $ k$$$. Note that adjacent nodes can belong to different components. Refer to the third sample.

N/A

N/A

A connected component is a set of nodes such that for any node in the set, you can reach all other nodes in the set passing only nodes in the set. In the first sample, it's optimal to choose the whole tree. In the second sample, you only have one choice (to choose node 1) because you can't choose 0 components. In the third sample, notice that we could've, for example, chosen only node 1, or node 1 and node 3, or even the whole tree, and the fraction would've had the same value (-1), but we want to maximize $ k $ . In the fourth sample, we'll just choose nodes 1 and 3.