#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,k,maxx,t[200005],all,f1,s2;
vector v[200005];
struct city{
int subtree,fl;
}c[200005];
int dfs(int dep,int p){
t[p]=1;
c[p].fl=dep;
c[p].subtree=1;
if(dep>n) return 1;
for(int i=0;i<v[p].size();i++){
if(t[v[p][i]]==0) c[p].subtree+=dfs(dep+1,v[p][i]);
}
return c[p].subtree;
}
bool cmp(city first,city second){
if(first.subtree!=second.subtree) return first.subtree<second.subtree;
return first.fl>second.fl;
}
signed main(){
cin>>n>>k;
for(int i=1;i<n;i++){
int a,b;
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
dfs(1,1);
f1=c[1].subtree;
sort(c+1,c+n+1,cmp);
for(int i=1;i<=k;i++){
all=all-c[i].subtree+c[i].fl;
}
cout<<all;
return 0;
}
题目描述
阿斯罗菲克帝国是大陆三大帝国中最北方的一个。费尔巴哈大帝认为工业发展程度才是一个帝国实力最重要的体现，因此他决定在帝国的 n 座城市里选定恰好 k 座城市建立工业基地。帝国的 n 座城市由 n-1 条双向通行的道路连接，且从任意一个城市都可以到达其它任意一座城市，大帝所在的 1 号城市就是帝国的首都。
每一年，大帝都会召开帝国工业大会，并下令每一个工业基地都派一位代表来首都参会，每一位代表都会走最短路径到达首都。但是由于代表待在工业基地的时间太久了，他们出来开会时总是想经过尽可能多的没有工业基地的城市。大帝体恤民情，因此希望选取 k 座城市建立工业基地后，每次开会的代表都能够经过尽可能多的没有工业基地的城市。
请问每年代表经过的没有工业基地的城市数量总和最多是多少。
输入格式
第一行两个整数 n 和 k，接下来 n-1 行每行两个整数表示一条双向通行的路径。
输出格式
输出一行一个整数表示答案。
样例输入
7 4 1 2 1 3 1 4 3 5 3 6 4 7
样例输出
7
样例输入
4 1 1 2 1 3 2 4
样例输出
2
样例输入
8 5 7 5 1 7 6 1 3 7 8 3 2 1 4 5
样例输出
9
数据规模
2≤n≤2⋅105，1≤k<n
