Computing maximum-cost subtree that uses at most k edges
Say our tree is $T = (V, E)$ with weight function $w : E \to \mathbb{Q}$ and $|V| = n$, and we are looking for the maximum-weight subtree with at most $k$ edges.
There is a $\Theta(nk^2)$-time and $\Theta(nk)$-space algorithm for binary trees that uses ideas from dynamic programming.
Idea: Store in every node $v$ the maximum weight obtainable using $i \in 1, \dots, k$ edges for a subtree rooted in $v$, as well as two pairs $(b_l, k_l)$ and $(b_r, k_r)$ for each $i$ that indicate if the left resp. right edges is chosen, and how many edges are chosen from each subtree; that is, $b_l + k_l + b_r + k_r = i$. Compute these numbers bottom-up; the leaves initialize with all zeroes.
Details:
for v ∈ V {
  for i ∈ [1..k] {
    v.maxWeight[i]   = 0
    v.chooseLeft[i]  = 0
    v.edgesLeft[i]   = 0
    v.chooseRight[i] = 0
    v.edgesRight[i]  = 0
  }
}

globalMax = [null, 0, -1]

def annotate(v) {
  if v is not a leaf {
    annotate(v.left)
    annotate(v.right)

    for i ∈ [1..k] {
      for j ∈ [0..i] {
        w  =   [j &gt; 0]   * w((v, v.left))  + v.left.maxWeight[max(0,j-1)]
             + [i-j &gt; 0] * w((v, v.right)) + v.right.maxWeight[max(0,i-j-1)]

        if w &gt; v.maxWeight[i] {
          v.maxWeight[i]   = w
          v.chooseLeft[i]  = min(j,1)
          v.edgesLeft[i]   = max(0,j-1)
          v.chooseRight[i] = min(i-j,1)
          v.edgesRight[i]  = max(0,i-j-1)
        } 
      }

      if v.maxWeight[i] &gt; globalMax[2] {
        globalMax = [v, i, v.maxWeight[i]]
      }
    }
  }  
}

annotate(T.root)

What remains then is to move top-down from globalMax[0] and follow the chooseX[_] links with edgesX[_] to construct the optimal subtree with globalMax[1] edges and weight globalMax[2].
Proof of correctness (by induction) and analysis are elementary.
The idea extends to trees of higher degree but then the factor $k^2$ changes to something more vicious; every node contributes something of the order of $k^{\operatorname{deg}(v)}$ then, if implemented naively.