健康监测计划

121 阅读 0 评论 80 点赞

我是靠谱客的博主害怕镜子，这篇文章主要介绍健康监测计划，现在分享给大家，希望可以做个参考。

题目链接：健康监测计划

显然从叶子贪心是最优的。于是我们可以想到先取叶子，然后把叶子删掉，然后继续取叶子。

一共取 k/2 次叶子，如果k是奇数，最后再任意取一个点即可。

所以我们树上拓扑即可。

AC代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e6+10;
int n,k,deg[N],dep[N],res;
vector<int> g[N]; queue<int> q;
signed main(){
	cin>>n>>k;
	for(int i=1,a,b;i<n;i++){
		scanf("%d %d",&a,&b); deg[a]++,deg[b]++;
		g[a].push_back(b),g[b].push_back(a);
	}
	if(k==0||k==1) return cout<<k,0;
	for(int i=1;i<=n;i++) if(deg[i]==1) q.push(i),dep[i]=1;
	while(q.size()){
		int u=q.front(); q.pop(); res++;
		for(int to:g[u]){
			dep[to]=max(dep[to],dep[u]+1);
			if(dep[to]<=k/2&&--deg[to]==1) q.push(to);
		}
	}
	cout<<min(n,res+k%2);
	return 0;
}