【ARC116E】题解

贪心 + 二分。

二分 /(mid/)，计算最少需要多少个消防站。

首先对点的深度 /(dep/) 进行排序，每次取当前最深的点 /(v/)。

找到与 /(v/) 的距离为 /(mid/) 的祖先 /(u/)，设立消防站。

可以证明这样是最优的：离 /(v/) 最近的消防站一定在 /(u/) 的子树中，并且能覆盖的点小于等于 /(u/) 能覆盖的点。

然后将 /(u/) 能覆盖的点都打上标记，跳到下一个 /(v/)。如果 /(v/) 已经被覆盖了就 /(continue/)。

至于为什么要取最深的点，感性理解一下，越深的点就越难满足要求。

放代码。

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

inline int read(){
	int x=0;
	char c=getchar();
	while(c<'0' || c>'9') c=getchar();
	while(c>='0' && c<='9') x=x*10+c-'0',c=getchar();
	return x;
}

int n,k,cnt,head[200002];

struct edge{
	int to,nxt;
}e[500002];

void addedge(int A,int B) {
	e[++cnt].to=B;
	e[cnt].nxt=head[A];
	head[A]=cnt;
}

int fa[200002],id[200002],dep[200002];

void dfs(int u,int f) {
	fa[u]=f,id[u]=u,dep[u]=dep[f]+1;
	for(int i=head[u];i;i=e[i].nxt) {
		int v=e[i].to;
		if(v==f) continue;
		dfs(v,u);
	}
}

bool cmp(int x,int y) {
	return dep[x]>dep[y];
}

bool vis[200002];

void solve(int u,int d,int f,int x) {
	if(d>x) return ;
	vis[u]=1;
	for(int i=head[u];i;i=e[i].nxt) {
		int v=e[i].to;
		if(v==f) continue;
		solve(v,d+1,u,x);
	}
}

bool check(int x) {
	for(int i=1;i<=n;i++) vis[i]=0;
	int tot=0;
	for(int i=1;i<=n;i++) 
		if(!vis[id[i]]) {
			tot++;
			if(tot>k) return 0;
			int u=id[i],dis=x;
			while(dis && fa[u]) u=fa[u],dis--;
			solve(u,0,0,x);
		}
	return 1;
}

int main() {
	n=read(),k=read();
	for(int i=1;i<n;i++) {
		int u=read(),v=read();
		addedge(u,v),addedge(v,u);
	}
	dfs(1,0);
	sort(id+1,id+n+1,cmp);
	int l=1,r=dep[id[1]],ans=r;
	while(l<=r) {
		int mid=(l+r)/2;
		if(check(mid)) r=mid-1,ans=mid;
		else l=mid+1;
	}
	printf("%d/n",ans);
	return 0;
}