P9603 [IOI2023] 山毛榉树 题解

· · 题解

提供一个自己做的思路。用到的性质比其他正解弱，但更容易想。

考虑单棵树的判定。初步读题后会得到两个性质：

  1. 一个点的儿子边权不能重复。
  2. 设所有权为 i 的边的较浅端点形成集合 S_i，则所有 S_i 形成一个“连续包含链”的结构。或者也可以从一个点的所有儿子边权角度等价描述。

这些性质都是 beautiful subtree 的必要条件，并且对于想象力不够丰富的选手来说，难以加强至充要条件。既然必要角度不行，那考虑充分角度——同样是一个很常见的套路，我们希望找到一种排列的构造，使得对于 beautiful subtree，构造出来的排列必定是 beautiful permutation；如果不是 beautiful subtree，那就不用考虑了。于是剩余要做的就是验证一遍题意中的条件即可。

归纳易证排列中越靠前的点子树 size 越大，因此先按 size 排序；如果两棵子树 size 相同，那么也归纳易证它们同构，因此它们的相对顺序只取决于它们各自父亲的相对顺序。因此可以在按 size 排序后再扫一遍，size 相同的按父亲在序列中的位置排序。这样可以做到 \mathrm{O}(n\log n) 单次判定。这些归纳易证的部分也都很直觉的。

对于原问题，一个有意思的猜想是，一棵 beautiful subtree 的子树也都是 beautiful 的。考试中当然可以直接 assert 然后交上去看看，不过这也是好证的。考虑 T(u) 对应的某个 beautiful permutation p。对于 v\in T(u)，将 p 中 {}\in T(v) 的点对应的子序列 p' 取出来，可以证明这就符合条件。因为对于某种权值的边，除去它的较深端点为 v 的情况以外（v 本身在 p' 中不贡献给计数器，故也不用考虑），其余该权值的边的两端点要么同时在 p' 中，要么同时不在 p' 中。因此扔掉 p' 以外的部分后，剩余的连边情况是保持不变的。

剩下的就是思想类似 [WC2018] 即时战略 的二分了。取出重链，在上面二分，然后往轻儿子递归。硬二分是 \mathrm{O}(n\log^3n) 的（代码），如果按全局平衡二叉树的方式带权二分，则是 \mathrm{O}(n\log^2 n) 的。这是因为考虑大小为 n 的树的第一轮二分，假设得到的根最浅 beautiful subtree 大小为 s，那么分 \ge 2s 和 <2s 的子树判定讨论，这轮二分的复杂度为 \mathrm{O}(n\log n+s\log^2 n)。接下来，剩余若干大小 \le n/2，和为 n-s 的子问题，这样分析下来就是 \log^2 的。