Explanation

Let's define $\texttt{best}[n][k]$ as the smallest edge set that connects a subtree of size $k$ rooted at node $n$ to the rest of the tree (It's undefined if such a subtree is impossible). The base cases for any node are as follows:

Then, when we're processing a specific node in the tree, we go through each of its children and incorporate the child's DP array into that of the current node. For each of these subtrees, we have 2 choices:

1. We don't include any of it, and add the edge connecting it and the current node to the current edge set we're processing.
2. We include some of it, and with that add the edge set stored in that subtree's DP array.

After that, we can simply go through each node and get the overall minimum edge set to get a city of size $k$.

Implementation

Copy
#include <algorithm>
#include <cassert>
#include <iostream>
#include <set>
#include <vector>

using std::cout;
using std::endl;
using std::pair;
using std::vector;