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

P4565 [CTSC2018] 暴力写挂 题解

题意简析

给出两棵树,每棵树有 \(n\) 个节点,求点对 \((x, y)\),使得下式最大化:

\[ \mathrm{deep}_x + \mathrm{deep}_y - \mathrm{deep}_{\mathrm{LCA}(x, y)} - \mathrm{deep'}_{\mathrm{LCA'}(x, y)}\]

\(n \le 366666\),边权可能为负。

思路解析

点分治/边分治 做法

1784X1419/graph.png

以点分治为例,在有根的情况下分治结构如上。设 \(root\) 为根节点,\(x\) 是当前的重心。

显然的,非 \(root\) 所在的其余子树 \(son_1,son_2,son_{\cdots}\) ,地位相等,正常合并。

对于 \(root\) 所在的部分,还需要分类讨论成 \(fa_1, fa_2,fa_{\cdots},root\) 这几种情况。

对于每个部分分别暴力统计,显然是会超时的。依据经验,做有根点分治/边分治题目时,要利用题目中的特殊性质。

  • 利用 LCA 与另一个点无关的性质,将影响范围缩小到系数。
  • 利用题目的特殊性质,将 \(root\) 所在的部分进行动态单点查询。
  • 有根的关键点不在 LCA(与本题无关)

为简化思考过程,以使用边分治为例。

对于跨越了中心边的点对 \((x, y)\),假设 \(y\) 处于根所在的连通块,且处在局部根为 \(r\) 的部分。则题中所要求的量转化为:

\[\mathrm{deep}_r + \mathrm{deep}_y - \mathrm{deep}_{\mathrm{LCA}(r, y)} - \mathrm{deep}_{\mathrm{LCA}(x', y)} \]

其中 \(x'\)\(y\) 无关,于是可以把这部分贡献直接计算到 \(y\) 上。

现在所求的量为带点权的第二棵树上的 LCA 深度的最小值。仍然建立虚树进行树形 DP。时间复杂度 \(\mathcal{O}(n \log^2 n)\)

但是如果我们不会写虚树呢?

树上启发式合并(dsu on tree)做法

我们可以有两种写法:

  1. 完全启发性合并,优点是十分短小精悍。(其实是我点分治调了两年半
  2. 先树链剖分选出重儿子,再暴力枚举轻儿子进行合并,优点是不会拆除父亲所在的部分。
http://www.wuyegushi.com/news/46.html

相关文章:

  • 第十二篇
  • 计算机网络——应用层 - 浪矢
  • 《第一节:跟着符映维学C语言---配置c语言开发环境》
  • 再见,大连
  • 影视软件集合分享
  • 7.26总结
  • geogebra 2 进阶
  • 20250726GF模拟赛
  • java学习
  • 深入解析Passkeys背后的密码学原理
  • CCF中学生计算机程序设计-基础篇-第一章-函数练习答案
  • 第二次总结——关系中的魔法语言
  • 2025.7 Solar应急响应-
  • 【计算几何】Largest Quadrilateral
  • 2025暑假qbxtNOIP实战梳理营Day1题目
  • 请求类型绑定响应类型
  • Untitled-1
  • AI代理性能提升实战:LangChain+LangGraph内存管理与上下文优化完整指南
  • GAIA基准测试介绍
  • 多项式全家桶(wjc)
  • 暑假qbxtNOIP实战梳理营Day1题目
  • 7月26日
  • 韦东山:嵌入式Linux全新系列教程之驱动大全(基于IMX6ULL开发板) 视频+资料(60G) 价值1299元
  • ARC200 小记
  • java第二十六天
  • 咕咕嘎嘎!!!(hard)
  • 主流PLC串口自由协议通信标准化
  • 20250726
  • Abp vNext -动态 C# API 实现原理解析
  • 健身营养——Stan Efferding