印刷企业网站模板企业网络营销推广平台

Problem - 1336A - Codeforces

Linova and Kingdom - 洛谷

 解析：

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

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

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

#include<bits/stdc++.h>
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;i<e[u].size();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<n;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<<res;return 0;
}