1600*A. Linova and Kingdom（DFS&优先队列&贪心）

Problem - 1336A - Codeforces

Linova and Kingdom - 洛谷

 解析：

        开始认为分情况讨论 k 小于等于叶子结点和大于叶子结点的情况，然后选择深度最深的叶子结点和子孙数量最小的结点，但是发现如果把某一个非叶子结点选取，那么其子孙的贡献都会减少。

        考虑贪心，首先DFS出每个节点的深度deep（根节点为 0 ）和每个节点的子孙结点个数 num（不带本身），这样如果某个结点被选取，那么其贡献为 deep - num ，所以我们选取最大的 k 个结点累计即可。

        此处贪心的正确性证明：如果我们要选择某个结点，那么他的所有子孙结点肯定要被选择。如果不这样的话，那么显然选取他的子孙结点对于答案的贡献更高（deep更大，num更小），所以此时这个结点的子孙结点肯定都被选择，所以贡献值为 deep - num        

#include
using namespace std;
#define int long long
const int N=2e5+5;
int n,k,dis[N];
vector<int>e[N];
priority_queue<int>q;
int dfs(int u,int deep,int fa){
	dis[u]=deep;
	if(e[u].size()==1&&u!=1){	//叶结点 
		q.push(dis[u]);
		return 1;
	}
	int cnt=0;
	for(int i=0;isize();i++){
		if(e[u][i]!=fa) cnt+=dfs(e[u][i],deep+1,u);
	}
	q.push(dis[u]-cnt);		//优先队列统计 
	return cnt+1;		//返回子孙结点个数 
}
signed main(){
	scanf("%lld%lld",&n,&k);
	for(int i=1;i
		int a,b;
		scanf("%lld%lld",&a,&b);
		e[a].push_back(b);
		e[b].push_back(a);
	}
	dfs(1,0,-1);	
	int res=0;
	while(k&&q.size()){
		res+=q.top();
		q.pop();
		k--;
	}
	cout<
	return 0;
}