CF2006E

alexdai · 2026-11-13 10:54:58 · 题解

前言

这篇题解是暴力数据结构卡过去的，没有技术含量 2\log 很不优雅。

前置知识。

• 点分治/点分树。
• 树直径的基础性质。
• 支持插入删除查询最小值的数据结构。

题意

给出一棵以 1 为根的树，满足 fa_i < i。

对于每个 i 询问对于由 1 \dots i 节点构成的无根树，能被最小深度为多少的满二叉树包含。

思路分析

记由 1 \dots i 构成的子树为 T_i，下标在下文中会被省略，简记为 T。

记两个点 u,v 的距离为 dis_{u,v}，表示两个点之间的简单路径经过对的边的数量。

记 D_u=\max_{v\not = u} dis_{u,v}。

1.观察满二叉树的性质

1. 从每个点的度数看：叶子的度数为 1，根的度数为 2，其他的度数都是 3。
2. 从直径看，深度为 d 的满二叉树的直径是 2(d-1)（直径为 \max_{i,j}dis_{i,j}）

2.无解情况

考虑存在 i\in T 满足 deg_i > 3，那么这颗树一定不可能被满二叉树包含（满二叉树不存在度数大于 3 的点），直接输出 -1 即可。

3. 考虑其他情况的构造

若任意 i\in T 都有 deg_i \leq 3，该怎么构造一个合法的满二叉树包含他呢？

随便找一个度数小于等于 2 的点 u 当作根节点，暴力将内部每个点的左右儿子补全到同一深度就行，显然这一定是以 u 为根的最小满二叉数。

4. 最优化构造结果

注意到以 u 为根构造的满二叉树的最小深度为 D_u+1。

所以最后对于 T_i 的最小满二叉数覆盖 = \min_{deg_u\leq 2}D_u+1。

5. 怎么求结果

首先观察 D_u 有性质： 到一个点最远的点一定是树直径的端点不知道性质的可以去做这个题

拓展一下：从 u 到 D_u 对应的 v 一定经过了树的直径至少一半的距离（也可以说是与至少一半的直径重合） ::::info[感性证明] 树上证明，正难则反，考虑反证

假设存在 u 到 D_u 对应的 v（后面全部简记为 v），与树的直径的交集小于树直径长度的一半（设另一个直径的端点记作 w，u 到 v 路径上第一次到树直径上的点记作 x）

可以发现 dis_{x,w} \geq 树直径距离的一半 \geq dis_{x,v}。

所以 dis_{u,v} \leq dis_{u,w} 与 v 是 D_u 对应的点矛盾（w 才是对应点）

讨论直径长度的奇偶性

• 直径长度为偶：

  • 设直径两端点为 x 和 y，中点记作 w，则可以考虑将 D_u 表示为 \max \{ dis_{u,x},dis_{u,y} \}。

  • 继续转化，考虑从 u 先走到直径中点，然后向两侧走则距离可以表示为 dis_{u,w}+dis_{w,x} = dis_{u,w}+\frac{dis_{x,y}}{2}。

• 直径长度为奇：

  • 设直径两端点为 x 和 y，中点记作 w_1,w_2，则可以考虑将 D_u 表示为 \max \{ dis_{u,x},dis_{u,y} \}。
  • 同理可以写作 \max(dis_{u,w_1},dis_{u,w_2})+\lfloor \frac{dis_{x,y}}{2} \rfloor。
  • 如果能把 \max 转化成 \min 那么维护起来就轻松很多。
  • 所以注意到 |dis_{u,w_1}-dis_{u,w_2}|=1；考虑将 \max 直接写成 \min 然后在外面在补上一个 1 就行也就是 \min(dis_{u,w_1},dis_{u,w_2})+\lceil \frac{dis_{x,y}}{2} \rceil。

综上所述：只要我们能维护 \min_{deg_u\leq 2}dis_{u,w} 那这道题就可以轻松解决。

数据结构维护信息

考虑从 T_i \to T_{i+1} 有且仅有 deg_{fa_{i+1}} 与 deg_{i+1} 变大 1。

所以问题可以转化为维护一颗树，每次标记一个点/删除一个点的标记，求从某个点到最近的标记点的距离是多少。

这个问题可以说是淀粉树的板子。

所以淀粉树暴力维护就可以了，也就是说 \min\{ 分治中心 x 到最近标记点的距离 + 分治中心 x 到 u 的距离 \}。

代码

时间复杂度 O(n\log^2n)，空间复杂度 O(n\log n)。