自动搬运

查看原文

来自洛谷，原作者为

	Marser 所有的苦难与背负尽头，都是行云流水般的此世光阴。

搬运于2025-08-24 22:22:04，当前版本为作者最后更新于2020-06-24 11:15:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

省选前最后一篇题解，感觉是个比较清新的贪心题。
Tweetuzki 神仙写了长链剖分和线段树，私以为不必要。

题意

定义点集 $V$ 为树的一个 $k-$独立集，当且仅当 $\forall x,y\in V,dis(x,y)\ge k$。
给定一棵大小为 $n$ 的树，求最大 $k-$独立集的大小。
$1\le n,k\le 2\times 10^5$。

题解

首先证明一个重要结论：对于以 $x$ 为根的子树，假设该子树的最大 $k-$独立集大小为 $f_x$，则 $x$ 子树对 $x$ 的父亲的贡献为 $f_x-1$ 或 $f_x$。

这个上界非常显然，不作赘述。
考虑证明这个下界。假设我们当前在求子树 $x$ 的答案，正在考虑合并子树 $y$ 的答案，我们令 $a,b$ 分别表示之前已经选中的点中，深度最小点和非严格次小点，$c,d$ 分别表示子树 $y$ 中深度最小点和非严格次小点，$d_1=dis(x,a),d_2=dis(x,b),d_3=dis(y,c),d_4=dis(y,d)$，显然存在 $d_1\le d_2,d_3\le d_4$。
$\because dis(a,b)\ge k$，$x$ 是 $a,b$ 的公共祖先
$\therefore d_1+d_2\ge k$
同理，$d_3+d_4\ge k$。

考虑这样一个贪心策略：

• 如果 $d_1+d_3+1\ge k$，则子树 $y$ 的所有节点都可以计入答案，取到上界 $f_y$。
• 如果 $d_1+d_3+1 < k$，
  • 如果 $d_3+1>d_1$，在最终答案中删除 $a$，加入子树 $y$ 的所有节点，方案仍然合法且最优，贡献为下界 $f_y-1$。
  • 如果 $d_3+1\le d_1$，加入子树 $y$ 除 $c$ 以外的所有节点，方案仍然合法且最优，贡献为下界 $f_y-1$。

对于后面两种策略，最优性不难证明。由于一定无法取到 $f_y$，因此只删去一个点一定是最优的。
对于 $d_3+1>d_1$ 的情况，最终只选择了 $b,c,d$ 三个点。由于 $dis(c,d)\ge k$，我们只需要证明 $dis(b,c)\ge k$ 即可。
$\because d_1<d_3+1,d_1+d_2\ge k$
$\therefore dis(b,c)=d_2+d_3+1 > d_2+d_1\ge k$
$\therefore dis(b,c)>k$

对于 $d_3+1\le d_1$ 的情况，最终选择了 $a,b,d$ 三个点，我们只需证明 $dis(a,d)\ge k$。
$\because d_3+1\le d1,d_3+d_4\ge k$
$\therefore dis(a,d)=d_1+d_4+1\ge d_3+d_4+2\ge k+2$
$\therefore dis(a,d)>k$

所以，每棵子树的贡献至少为 $f_x-1$。

我们在 dfs 的过程中维护每棵子树最大 $k-$独立集的大小 $f_x$，以及所有取到最大值的方案中，深度最小的点的最大深度 $dep_x$。

• 当 $dep_x+dep_y+1\ge k$ 时，$dep_x\gets \min(dep_x,dep_y+1)$，$f_x\gets f_x+f_y$。
• 当 $dep_x+dep_y+1< k$ 时，$dep_x\gets \max(dep_x,dep_y+1)$，$f_x\gets f_x+f_y-1$。

合并完所有子树后，再判断一下能不能选根节点即可。时间复杂度 $O(n)$，代码极为简单。

代码

#include<bits/stdc++.h>
#define reg register
typedef long long ll;
using namespace std;
const int MN=2e5+5;
int to[MN<<1],nxt[MN<<1],h[MN],cnt;
inline void ins(int s,int t){
	to[++cnt]=t;nxt[cnt]=h[s];h[s]=cnt;
	to[++cnt]=s;nxt[cnt]=h[t];h[t]=cnt;
}
int n,m,f[MN],dep[MN];
void dfs(int st,int fa=0){
	dep[st]=1e9;
	for(reg int i=h[st];i;i=nxt[i])
		if(to[i]!=fa){
			dfs(to[i],st);
			if(dep[st]+1+dep[to[i]]>=m){
				f[st]+=f[to[i]];
				dep[st]=min(dep[st],dep[to[i]]+1);
			}
			else{
				f[st]+=f[to[i]]-1;
				dep[st]=max(dep[st],dep[to[i]]+1);
			}
		}
	if(dep[st]>=m)f[st]++,dep[st]=0;
}
int main(){
	scanf("%d%d",&n,&m);
	for(reg int i=2,x;i<=n;i++)
		scanf("%d",&x),ins(i,x+1);
	dfs(1);printf("%d\n",f[1]);
	return 0;
}