C. Linova and Kingdom (DFS&贪心）

C. Linova and Kingdom (DFS&贪心）

题目传送门

思路：

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
#define mst(a) memset(a,0,sizeof a)
vector<int>ans;
vector<int>e[N];
int dfs(int u,int fa,int d){
	int sz=1;
	for(auto v:e[u]){
		if(v==fa) continue;
		sz+=dfs(v,u,d+1);
	}
	ans.push_back(d-sz+1);
	return sz;
}
int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1,u,v;i<n;i++){
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1,0,0);
	sort(ans.begin(),ans.end(),greater<int>());
	ll res=0;
	for(int i=0;i<k;i++)
	{ 
		res+=ans[i];
	}
	printf("%lld\n",res);
	return 0;
}