解析:
开始认为分情况讨论 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;i
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
- 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;
- }
-
相关阅读:
【python】(七)python内置装饰器: @classmethod和@staticmethod
Charge Generation (Liberation) 、Decay Rate
C 语言 时间函数使用技巧(汇总)
Java方法的使用
nacos注册中心AP核心源码
手把手教你制作登录、注册界面 SpringBoot+Vue.js(cookie的灵活运用,验证码功能)
pyqt5移动鼠标时显示鼠标坐标
Android通知Notification使用全解析,看这篇就够了
QT软件开发-基于FFMPEG设计视频播放器-支持软解与硬解(二)
10分钟学会Hive之用户自定义函数UTF开发
-
原文地址:https://blog.csdn.net/JungleZRD/article/details/133779601