参考:Codeforces Round #635 Editorial
首先要知道的规律是如果一个城市为工业城市,那么它的所有子节点也肯定为工业城市。可以通过反证法证明。
那么我们可以得到每一个旅游城市的贡献为(子树大小 - 结点深度),证明方法可以查看官方题解。
没有思路的话,可以先推推其中的规律,再根据得到的规律进行求解。如果可以将对整个图的分析化为对一个点独立的分析,那么就很容易了。
// Created by CAD on 2020/4/17.
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+5;
vector<int> g[maxn];
int son[maxn],d[maxn];
void dfs(int x,int fa,int deep){
son[x]=1;
for(auto i:g[x])
if(i!=fa) dfs(i,x,deep+1),son[x]+=son[i];
d[x]=son[x]-deep;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,k; cin>>n>>k;
for(int i=1,x,y;i<=n-1;++i)
cin>>x>>y,g[x].push_back(y),g[y].push_back(x);
dfs(1,0,1);
sort(d+1,d+n+1,greater<int>());
ll sum=0;
for(int i=1;i<=n-k;++i) sum+=d[i];
cout<<sum<<"\n";
return 0;
}