p3523 sol（POI2011 DYN）

AllenJYL · 2024-12-19 19:41:56 · 题解

套路地二分答案 w 转化为判定。实质上就是选出 m 个点使得每个关键点的 w 邻域中至少有一个选中点。

由于选点也满足单调性，我们不妨计算出使得每个关键点的 w 邻域中至少有一个选中点的选点方案至少需要多少个点。

考虑递推。设计状态 f_i 表示 i 子树内距离 i 最远的还不合法的关键点的距离。为了转移，还需要设计 g_i 表示 i 子树内距离 i 最近的选中点的距离，以及 h_i 表示 i 子树内选中的点数。

考虑到合并子树，首先令

其中 v 是 i 的儿子。特别地

• 若 i 子树内没有不合法关键点则 f_i=-\infty；
• 若 i 子树内没有选中点则 g_i=+\infty。

分两种情况考虑：

• 若 d_i=1，说明 i 为关键点，此时
  • 若 g_i\le w，那么 i 合法，不需要额外考虑；
  • 否则，i 当前不合法，计入 f_i，即 f_i\larr \max(0,f_i)；

• 否则，i 不为关键点，此时显然能不选择其就不选择其，因为越浅的节点可以覆盖的其他子树内的节点数就越多，将选择的点留到更浅的节点上更优，所以

  • 若必须选择其，则 h_i\larr h_i+1，g_i\larr 0；
  • 否则，不需要额外考虑；

  判断必须选择当且仅当 f_i=w。

额外地，如果 f_i+g_i\le w，则令 f_i=-\infty。

初值容易判断。