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

**题意** ： 给出一棵 $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)$。 ```cpp #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; } ```