Given a Binary Tree with N nodes, and each of the nodes have a value associated to them A[i] (values not necessarily be distinct). Find the minimum cost of a subtree with K connected number of nodes in the tree.

Now, cost of a sub tree with k nodes can be :

1. Simply the sum of all the k nodes
2. (Sum of K Nodes) / (height of the subtree)

We need to minimize this cost.

1 and 2 are separate questions. I could come up with O(N x K x K) approach for problem 1.

Can someone help with any better solutions of Problem 1 and 2?