当前位置: 首页 > news >正文

神秘专题训练之老题补做

2024

在我的深刻思考下,我决定先开xtq的杂题选讲,我能归来吗?

杂题选讲 by xtq

unknown

给定一棵带权树和一个 \(k\),选 \(k\) 个点标记,使得对于每个点(可以不是标记点)到最近的标记点的距离的最大值最小。\(n \leq 10^5\)

先二分答案。考虑怎么 \(check\)。以下用“放”表示标记,\(mid\) 是二分的答案。

\(d_x\) 表示 \(x\) 的子树内至少放 \(d_x\) 个能使得我再在 \(x\) 处再放一个就能让子树全满足,\(f_x\) 表示再满足 \(d_x\) 最小的前提下 \(x\) 和它子树内最近的标记点的距离最小是多少(这里的地位是先让 \(d_x\) 最小然后再让 \(f_x\) 最小),\(g_x\) 表示如果 \(f_x\) 寄了(\(>mid\) 了)那么对于那些假如只标记那 \(d_x\) 点就无法满足的点中最深的那个点距离 \(x\) 是多少。

考虑如何合并子树。

首先对于 \(d_x\) 那些 \(d_{son}\) 是最基础的得加上,这个就是简单求和。

然后对于 \(f_{son}\) 考虑如果把这个儿子连向 \(x\) 的那个边加进来以后是否依旧 \(\leq mid\),如果是那么更新一下 \(f_x\)。否则的话如果当前的 \(f_{son}+w\) 全都 \(>mid\),那么就要更新变成 \(g_x=0\)\(f_x\) 照常更新取 \(min\)

接下来是 \(g\),那么这个 \(g\) 就是我们要满足的,那么子树内显然是不行了,那么肯定是子树外的标记点覆盖它,考虑肯定是另一棵子树内的一个标记点转移过来,我们肯定希望这个标记点到 \(x\) 的距离最小(因为你考虑这个 \(son'\) 子树内的标记点到那个不满足的 \(g_son\) 的距离是\(f_{son'}+w_{son'}+g_{son}+w_{son}\)),那么你就看一下 \(f_{son'}+w_{son'}+g_{son}+w_{son}\) 这个东西是不是 \(\leq mid\) 的即可,这下就没有影响,反正都解决了。

然后如果不能覆盖到,也就是 \(f_{son'}+w_{son'}+g_{son}+w_{son}>mid\),此时如果 \(g_{son}+w_{son} \leq mid\),那么显然在 \(x\) 再放一个就完了,那么你更新一下 \(g_x\) 的值就行(用 \(g_{son}+w_{son}\))。如果 \(g_{son}+w_{son}>mid\),那么在 \(u\) 放也会寄。我们设 \(g_{son}\) 的那个最深的点是 \(p\),此时就得在 \(p-x\) 的路径上选一个点使得能覆盖到 \(p\) 并且距离 \(x\) 最近的点,这个也是好维护的,维护以后更新一下新的 \(f_x\) 并且把 \(d_x\) 加一即可。

http://www.hskmm.com/?act=detail&tid=24551

相关文章:

  • 全球 whk 水平下降 998244353 倍,而你不变
  • 202510做题记录
  • 全球 wkh 水平下降 998244353 倍,而你不变
  • python 基础问题汇总
  • 球球大作战
  • 全球 OI 水平下降 998244353 倍,而我不变
  • VulnHub-Raven2 靶场 wp
  • javaScript的构造函数和java的构造函数区别
  • 天一生水 地六成之
  • P14041 [PAIO 2025] Towers
  • 根号分治简单解说
  • 哈希简单解说
  • Say 题选记(9.28 - 10.4)
  • Excel表设置为细框线
  • 前端学习教程-VIte整合ECharts
  • const不可改变解释
  • macOS Sequoia 15.7.1安全更新:修复字体解析器内存损坏漏洞
  • AtCoder Beginner Contest 426 ABCDEF 题目解析
  • 数学
  • 前端学习教程-ElementPlus 教程
  • AI训练的悖论:为什么越追求准确率越会产生幻觉?
  • 信奥大联赛周赛(提高组)#2516-S 赛后盘点
  • PSRAM 是什么
  • Debian 13 eza 安装与常用参数
  • Syncthing 2.0 版本开机自启
  • 鲜花 10.4:【半 whk 向】临项交换法贪心
  • 前端学习教程-Pinia 教程
  • 布谷娱乐直播架构源码开发实用功能:技术驱动更迭的创新体验
  • Bean生命周期
  • 回忆QQ空间有感