C - Linova and Kingdom
參考: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;
}