Find a maximum tree subgraph with given number of edges that is a subgraph of a tree

Question

So a problem is as follows: you are given a graph which is a tree and the number of edges that you can use. Starting at v1, you choose the edges that go out of any of the verticies that you have already visited.

An example:

In this example the optimal approach is:

for k==1 AC -> 5
for k==2 AB BH -> 11
for k==3 AC AB BH -> 16

At first i though this is a problem to find the maximum path of length k starting from A, which would be trivial, but the point is you can always choose to go a different way, so that approach did not work.

What i though of so far:

1. Cut the tree at k, and brute force all the possibilites.

2. Calculate the cost of going to an edge for all edges. The cost would include the sum of all edges before the edge we are trying to go to divided by the amount of edges you need to add in order to get to that edge. From there pick the maximum, for all edges, update the cost, and do it again until you have reached k.

The second approach seems good, but it reminds me a bit of the knapsack problem.

So my question is: is there a better approach for this? Is this problem NP?

EDIT: A counter example for the trimming answer:

Answer 1

This code illustrates a memoisation approach based on the subproblem of computing the max weight from a tree rooted at a certain node.

I think the complexity will be O(kE) where E is the number of edges in the graph (E=n-1 for a tree).

edges={}
edges['A']=('B',1),('C',5)
edges['B']=('G',3),('H',10)
edges['C']=('D',2),('E',1),('F',3)

cache={}
def max_weight_subgraph(node,k,used=0):
    """Compute the max weight from a subgraph rooted at node.
    Can use up to k edges.
    Not allowed to use the first used connections from the node."""
    if k==0:
        return 0
    key = node,k,used
    if key in cache:
        return cache[key]
    if node not in edges:
        return 0
    E=edges[node]
    best=0
    if used<len(E):
        child,weight = E[used]
        # Choose the amount r of edges to get from the subgraph at child
        for r in xrange(k):
            # We have k-1-r edges remaining to be used by the rest of the children
            best=max(best,weight+
                     max_weight_subgraph(node,k-1-r,used+1)+
                     max_weight_subgraph(child,r,0))
        # Also consider not using this child at all
        best=max(best,max_weight_subgraph(node,k,used+1))
    cache[key]=best
    return best

for k in range(1,4):
    print k,max_weight_subgraph('A',k)