https://codeforces.com/contest/1337/problem/C
2.Idea
Sort by {Depth - Child Number}, and pick k vertices.
3.Source
int n, k;
vector<int> adj[N];
int dist[N];
bool visited[N];
int child[N];
bool col[N];
int dist2[N];
struct City {
int num, child, dist;
bool operator < (const City &a)const {
return dist - child < a.dist - a.child;
}
} Cities[N];
void getChild(int k)
{
//cout << k << endl;
visited[k] = true;
for (int i = 0; i < adj[k].size(); i++) {
int u = adj[k][i];
if (visited[u] == 0) {
getChild(u);
child[k] += (1 + child[u]);
}
}
}
void colorCities()
{
for (int i = 0; i < n; i++) {
Cities[i].num = i;
Cities[i].child = child[i];
Cities[i].dist = dist[i];
}
sort(Cities, Cities + n);
for (int i = 0; i < n - k; i++) {
int t = Cities[i].num;
col[t] = true;
}
}
int main()
{
cin >> n >> k;
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--; v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
// get dist
memset(visited, 0, sizeof visited);
queue<P> q;
q.push(P(0, 0));
while (!q.empty()) {
int v = q.front().first;
int d = q.front().second;
q.pop();
visited[v] = 1;
dist[v] = d;
for (int i = 0; i < adj[v].size(); i++) {
int u = adj[v][i];
if (visited[u] == 0 && dist[u] == 0) {
q.push(P(u, d + 1));
}
}
}
//get child
memset(visited, 0, sizeof visited);
getChild(0);
//color
colorCities();
//count
memset(visited, 0, sizeof visited);
queue<P> q1;
q1.push(P(0, 0));
while (!q1.empty()) {
int v = q1.front().first;
int d = q1.front().second;
q1.pop();
visited[v] = 1;
dist2[v] = d;
if (col[v]) d++;
for (int i = 0; i < adj[v].size(); i++) {
int u = adj[v][i];
if (visited[u] == 0) {
q1.push(P(u, d));
}
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
if (col[i] == 0) ans += dist2[i];
}
cout << ans << endl;
return 0;
}
