command_block 的博客

command_block 的博客

[??记录]P6574 [BalticOI 2017] Cat in a tree

posted on 2021-11-17 22:04:07 | under 记录 |

题意 : 给出一棵 $n$ 个点的树,选出一些点使得两两距离 $\geq d$ ,最大化选出的点数。

$n\leq 2\times 10^5$ ,时限$\texttt{1s}$。


大力 DP 并长剖+线段树优化可以无脑地做到 $O(n\log n)$。

然而有比较简洁的贪心做法。

对于一条边 $u,v$ ,假设我们求出 $u,v$ 两侧的最优解,然后将 $u,v$ 连上。

若一方的两个最浅点为 $a,b$ ,另一方两个最浅点为 $c,d$ ,深度分别 $d_a,d_b,d_c,d_d$ ,不妨设 $d_a\leq d_b,d_c\leq d_d$ 。

显然有 $d_a+d_b,d_c+d_d\geq d$ ,故 $d_b,d_d\geq d/2$ 。

因此必然有 $d_b+d_d\geq d$ ,两者不冲突。所有可能的冲突都与 $a,c$ 之一有关。

可以证明只可能去除 $a,c$ 之一。

具体地,若 $a$ 有矛盾 $d_a+d_d<d$ ,则 $b$ 不可能再有矛盾 $d_b+d_c<d$ ,与 $d_a+d_b+d_c+d_d\geq 2d$ 矛盾。


记 $f_u$ 表示 $u$ 子树内的最优解,$dis_u$ 表示最优方案中到 $u$ 最近点距离的最大值。

合并子树 $u,v$ 时:

  • 若 $dis_u+dis_v+1\geq d$ ,则 $f_u\leftarrow f_u+f_v,\ dis_u\leftarrow\min(dis_u,dis_v)$

  • 若 $dis_u+dis_v+1<d$ ,则 $f_u\leftarrow f_u+f_v-1,\ dis_u\leftarrow\max(dis_u,dis_v+1)$

    这个 $\max$ 需要说明一下,假设 $dis_u$ 较小,被舍去。而 $u$ 方的次大值 $x$ 必然 $\geq dis_v+1$ ,否则 $x,dis_u$ 产生矛盾。

合并完所有子树之后,再判定能否选根节点。

复杂度 $O(n)$。

#include<algorithm>
#include<cstdio>
#include<vector>
#define MaxN 205000
using namespace std;
const int INF=1000000000;
vector<int> g[MaxN];
int n,lim,f[MaxN],dis[MaxN];
void dfs(int u,int fa)
{
  dis[u]=INF;
  for (int i=0,v;i<g[u].size();i++)
    if (fa!=(v=g[u][i])){
      dfs(v,u);
      if (dis[u]+dis[v]+1<lim){
        f[u]+=f[v]-1;
        dis[u]=max(dis[u],dis[v]+1);
      }else {
        f[u]+=f[v];
        dis[u]=min(dis[u],dis[v]+1);
      }
    }
  if (dis[u]>=lim){f[u]++;dis[u]=0;}
}
int main()
{
  scanf("%d%d",&n,&lim);
  for (int i=2,fa;i<=n;i++){
    scanf("%d",&fa);
    g[fa+1].push_back(i);
  }dfs(1,0);printf("%d",f[1]);
  return 0;
}