自动搬运

查看原文

来自洛谷，原作者为

	tommymio Cruel world

搬运于2025-08-24 21:49:49，当前版本为作者最后更新于2020-03-16 20:26:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

从我认真记录以来第 $3$ 道由于读错题面而GG的题目（

观察题目，显然有一个外层二分的模型，二分距离的最大值作为上界。

问题就转化成了：一棵树上选 $m$ 个点，使得这 $m$ 个点与关键节点的最小距离不超过$mid$。

然后发现上面那个问题是不好解决的，根据二分判定，问题还可以进一步转化：一棵树上选 $tot$ 个点，使得这 $tot$ 个点与关键节点的最小距离不超过mid，最小化 $tot$。

这大概就是一个最小点覆盖的问题，用最少的点覆盖所有关键节点。

下面是我对于这道题目给出的一些定义：

称点 $x$ 覆盖点 $y$，当且仅当点 $x$ 与点 $y$的距离不超过给定的距离限制 $mid$。（以下就直接使用这两个概念，不再重复）

而最小点覆盖的定义是，对于每个关键节点 $y$ ，选定的 $tot$ 个点中有任意一个点 $x$ 到点 $y$ 的距离不大于给定的距离限制 $mid$，令 $tot$ 最小。

选定节点为你选择的节点，关键节点同题目定义。

接下来怎么解决呢？我们发现，如果一棵子树的根 $root$ 到最远的关键节点的距离小于 $mid$ ，那意味着这整棵子树是可以被这个 $root$ 覆盖的.并且如果以这种方式自底而上递归，一定能够得出一种方案来解决这个问题，但这个方案很明显不是最优解。

为什么呢？经过观察，我们可以发现，如果每次贪心的采取这种方式，我们每次会重复覆盖一些点，这样就会得不到最优解，那怎么办呢？我们可以记录下每次未被之前覆盖的关键节点到 $root$ 的最远距离，这样就可以减少掉多余的覆盖。

为什么说叫做减少多余的覆盖，而不是消除所有多余的覆盖呢？经过思考，我们可以发现，我们覆盖整颗子树 $root$ 时，不一定会选定 $root$ 作为用来覆盖这棵子树的点，我们可能会使用 $root$ 下的子孙 $y$ 来覆盖整颗子树，从而得到更优解。

根据上面的两个思路，我们就可以想到设 $f_{root}$ 表示距 $root$ 最远的未被覆盖的关键节点到 $root$ 的距离，$g_{root}$为 $root$ 到该子树下的被选定节点的最小距离。

DP过程就为：

• 初值：$f_{root}=-\infty,g_{root}=\infty$

• $f_x=\max \{f_y+1\}$，$g_x=\min\{f_y+1\}$

这样就结束了么？是不是很好奇为什么没有用到$d_i$？

我们还需要特判几种情况以及统计最小点覆盖。

• 当$f_x+g_x<=mid$ ，说明只用已选定节点中到 $x$ 距离最小的点就能够覆盖到最远的关键节点，整棵子树自然可以被完全覆盖。就有$f_x=-\infty$
• 当$f_x = mid$ ，说明最远的关键节点到根的距离刚好为$mid$，如果我们此时不将 $x$ 节点作为被选定节点，那么这个最远的关键节点将永远无法被覆盖。所以我们只能选定 $x$ 节点作为选定节点。既然选定了我们也要把它计算到 $tot$ 里。$f_x=-\infty$，$g_x=0$，$++tot$(自身被选定了显然是 $0$ 啊)
• 当$g_x>mid \text{且} d_i=1$，说明到 $root$ 最近的选定节点无法被使用，$root$ 自身也是一个关键节点。所以这棵子树无法被它的子孙覆盖，也就是说这棵子树可能无法被完全覆盖，可以丢给它的父亲处理。$f_x=\max(f_x,0)$ (想一想，为什么)。

以上DP过程大概解释一下，当我们将 $f_x$ 置为 $-\infty$ 时，说明该子树已被完全覆盖，就不会影响其祖先的 $f$ 值。

一定要记得特判根啊！！！

Show the Code

#include<cstdio>
//f[i] 以i为根的子树未被覆盖的最远距离
//g[i] 以i为根的子树被选择的点的最近距离
#define max(a,b) ((a)>(b)? (a):(b))
#define min(a,b) ((a)<(b)? (a):(b))
typedef long long ll;
const ll inf=1e8;
int n,m,res=0,cnt=0,tot=0;
int b[300005];
ll f[300005],g[300005];
int h[300005],to[600005],ver[600005];
inline int read() {
	register int x=0,f=1;register char s=getchar();
	while(s>'9'||s<'0') {if(s=='-') f=-1;s=getchar();}
	while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
	return x*f;
}
inline void add(int x,int y) {
	to[++cnt]=y;
	ver[cnt]=h[x];
	h[x]=cnt;
}
void dfs(int x,int fa,int mid) {
	f[x]=-inf;g[x]=inf;
	for(register int i=h[x];i;i=ver[i]) {
		int y=to[i];
		if(y==fa) continue;
		dfs(y,x,mid);
		f[x]=max(f[x],f[y]+1);
		g[x]=min(g[x],g[y]+1);
	}
	if(f[x]+g[x]<=mid) f[x]=-inf;//不需要再被覆盖，直接置为-inf
	if(g[x]>mid&&b[x]==1) f[x]=max(f[x],0);//当前无法覆盖，需要父亲帮忙
	if(f[x]==mid) f[x]=-inf,g[x]=0,++tot;//不需要再被覆盖
}
int check(int x) {
	tot=0;
	dfs(1,-1,x);
	if(f[1]>=0) ++tot;
	return tot<=m;
}
int main() {
	n=read(),m=read();
	for(register int i=1;i<=n;++i) b[i]=read();
	for(register int i=1;i<n;++i) {
		int x=read(),y=read();
		add(x,y);add(y,x);
	}
	int L=0,R=n;
	while(L<=R) {
		int mid=L+R>>1;
		if(check(mid)) {R=mid-1;res=mid;}
		else {L=mid+1;}
	}
	printf("%d\n",res);
	return 0;
}