Statement 1: There is no exist the tree with sum of depths of all vertices more than unary tree.

Statement 2: There is no exist the tree with sum of depths of all vertices less than balanced tree.

Let's create unary tree for default. Sum of depth for this tree — is the sum of ariphmetic progression. We must decrease it to the d. Fix the deepest vertex. Fix the top vertex of the tree. If we can't attacth the lower vertex to the higher because the sum of depth will be smaller than d, it means that we must deepen the upper vertex. And as we go from top to bottom the difference on every step decreases exactly 1. It means that there isn't exist the better solution.

Add to these the condition that every layer must be not greater than 2 size of previous layer and this will be a solution.

If we use 2 pointers in E, complexity will be O(n). https://mirror.codeforces.com/contest/1311/submission/71823186

For G alternative solution is existed.

Let define segment structure which consists of sum on this segment, gap, previous segments and next segment. Structure's comparer is: what gap is needed to merge with previous segment. Segments are stored in set.

Go from left to right. After step we must add new segment with parameters: gap = (d[i] — d[i — 1]) ^ 2, sum = 2 * m — c[i] — c[i — 1]. After it we merge all segments in set, which are needed gap < current gap to merge with prev. Let's remove mergeable, prev and next for mergeable and add mergeable and next for mergeable segments to set (it's needed for updating set, comparer for next was changed).

Answer is the best answer after each merge, segment's creating, best of m — c[i] and zero. Asymptotics — O(N * log(N)).

Code: 49039327