Given a full binary tree with n = 2^h - 1 vertices, each non-leaf vertex i has two children 2i+1 and 2i+2.

You are also given an array w, which stores the weights of the edges. e.g.

• w[2i] stores the weight of the edge between nodes i and 2i+1;
• w[2i+1] stores the weight of the edge between nodes i and 2i+1;

The problem asks you to select k vertices so as to maximize the sum of the edge weights among this subset of size k. Note that an edge can only be included when both vertices at its ends are selected in the subset.

I have been trying to solve this problem but have no clue. Can it be solved with DP? Thank you so much!

Example:
n = 7, k = 3, w= [16,5,11,17,11,10] => result = 33
(This means there are 7 vertices in the full binary tree, i.e. 3 layers and the subset size is 3)