题解 P6574 【[BOI 2017] Cat in a tree】

· · 题解

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

题意

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

### 题解 首先证明一个重要结论：对于以 $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。

考虑这样一个贪心策略：

对于后面两种策略，最优性不难证明。由于一定无法取到 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。

合并完所有子树后，再判断一下能不能选根节点即可。时间复杂度 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;
}