min vertex cover to access k edges in a tree
There is a $\mathcal{O}(nk)$ DP approach.

Call an edge covered if we select a vertex next to it. Root the tree at an arbitrary vertex $r$. Define $DP[i][b][t]$ as the maximum number of edges in the subtree of node $i$ that can be covered by selecting at most $t$ nodes from the subtree. If $b = 0$ we are not allowed to select node $i$, and if $b = 1$ we must select it.

If we calculate this DP, we can solve the problem, as the minimum number of nodes to cover $k$ edges is the smallest $t$ for which $max(DP[r][0][t], DP[r][1][t]) \geq k$. Further note that it suffices to only calculate the $DP$ for $t \leq k$, as any $k &lt; n$ nodes cover at least $k$ edges.

To give the recurrence to calculate the DP, we first give the knapsack-function: let $K(V_{1}, \dots, V_{m})$ be an array such that 

\begin{equation*}
K(V_{1}, \dots, V_{m})[t] = \max_{t_{1} + \dots + t_{m} = t} \sum_{j = 1}^{m} V_{j}[t_{j}]
\end{equation*}

Note that $K(K(V_{1}, \dots, V_{m-1}), V_{m}) = K(V_{1}, \dots, V_{m})$, and that $K(A, B)$ can be directly calculated by the above formula in $\mathcal{O}(|A| \cdot |B|)$ time. Hence calculating $K(V_{1}, \dots, V_{m})$ takes $\mathcal{O}(\sum_{i = 2}^{m} |V_{i}| \sum_{j = 1}^{i-1} |V_{j}|)$ time regardless of the order we combine the sets in. If we are interested in only the first $k$ values of the DP, the complexity drops to $\mathcal{O}(\sum_{i = 2}^{m} |V_{i}| \min(k, \sum_{j = 1}^{i-1} |V_{j}|))$

Let $C_{i}$ be the set of children of node $i$, and $C_{ij}$ be the $j$th child of $i$. Then 
\begin{gather*}
DP[i][0][t] = K(V_{1}, \dots, V_{|C_{i}|})[t]\\
DP[i][1][t] = |C_{i}| + K(V'_{1}, \dots, V'_{|C_{i}|})[t-1]
\end{gather*}
Where
\begin{gather*}
V_{j}[t] = \max(DP[C_{ij}][0][t], DP[C_{ij}][1][t] + 1)\\
V'_{j}[t] = \max(DP[C_{ij}][0][t], DP[C_{ij}][1][t])\\
\end{gather*}
Calculating the answer with this recursion takes $\mathcal{O}(nk)$ time. Informally this is because over the course of the algorithm, we combine single-element DPs into a DP representing the whole tree. We do at most $\frac{n}{k}$ combinations of sets of size $k$, and any element costs us at most $2k$ time (if element $x \in A$ costs us $|B|$ time when calculating $K(A, B)$) before it gets merged into a set of size $k$, so the total amount of work is at most $\mathcal{O}(k^{2} \frac{n}{k} + k n) = \mathcal{O}(nk)$. This is easy but tedious to formalise with induction.

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;tuple&gt;
using namespace std;
const int INF = (int)1e9 + 7;

vector&lt;int&gt; knapsack(const vector&lt;int&gt; a, const vector&lt;int&gt; b, int k) {
    int n = a.size();
    int m = b.size();
    vector&lt;int&gt; c(n+m-1, -INF);
    for (int i = 0; i &lt; n; ++i) {
        for (int j = 0; j &lt; m; ++j) c[i+j] = max(c[i+j], a[i] + b[j]);
    }
    if (c.size() &gt; k) c.resize(k);
    return c;
}

pair&lt;vector&lt;int&gt;, vector&lt;int&gt;&gt; dfs(int i, int p, int k, const vector&lt;vector&lt;int&gt;&gt;&amp; g) {
    vector&lt;int&gt; dp0 = {0, 0};
    vector&lt;int&gt; dp1 = {-INF, (int)g[i].size() - (p != -1)};
    for (auto t : g[i]) {
        if (t == p) continue;
        vector&lt;int&gt; dp0_t, dp1_t;
        tie(dp0_t, dp1_t) = dfs(t, i, k, g);
        int m = dp0_t.size();

        vector&lt;int&gt; off0(m), off1(m);
        for (int j = 0; j &lt; m; ++j) off0[j] = max(dp0_t[j], dp1_t[j] + 1);
        for (int j = 0; j &lt; m; ++j) off1[j] = max(dp0_t[j], dp1_t[j]);
        dp0 = knapsack(dp0, off0, k+1);
        dp1 = knapsack(dp1, off1, k+1);
    }
    return {dp0, dp1};
}

int minCover(int k, const vector&lt;vector&lt;int&gt;&gt;&amp; g) {
    vector&lt;int&gt; dp0, dp1;
    tie(dp0, dp1) = dfs(0, -1, k, g);
    for (int i = 0;; ++i) {
        if (max(dp0[i], dp1[i]) &gt;= k) return i;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin &gt;&gt; n &gt;&gt; k;

    vector&lt;vector&lt;int&gt;&gt; g(n);
    for (int i = 0; i &lt; n-1; ++i) {
        int a, b;
        cin &gt;&gt; a &gt;&gt; b;
        --a; --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    int t = minCover(k, g);
    cout &lt;&lt; t &lt;&lt; '\n';
}