题解：P11234 [CSP-S 2024] 擂台游戏

山田リョウ · 2024-10-27 17:14:53 · 题解

害我写检讨的垃圾题，强烈谴责低素质出题人！！！

（方便起见，我们认为加第 i 个人就是第 i 个时刻）

首先一眼会得出一个在线加点的 O(T n\log n) 做法，并感觉出应该可以通过出色的剪枝摊掉变成 O(T n)，但是我失败了。

比较严重的问题其实是出在每层擂主胜利条件是有区别的，致使从儿子向父亲转移时还需要删一部分不符合条件的点，这也太难了。

直觉告诉我可以再丢些东西摊掉，例如一个人只会被删 O(1) 次，但是还是失败了。因为你需要动态维护些类区间和的东西，这个无法避免复杂度中 \log n 的出现。

但是这并不是没有用的，它启发我们每个人能作为最终胜利者的区间其实是 O(1)（具体来说最多是 2 个） 个的，所以考虑枚举人。

只不过在一切之前最好先把一些可能导致细节过多的东西消去，例如不同前缀需要跑的轮数可能是不一样的。但是考虑到 \sum\limits_{k=0}^{n-1}2^k=2^n-1，故枚举轮数即可。

固定轮数后每个人可以成为胜者是一个前缀，于是我们只需要找到使得他依然可以成为胜者的最大时间点即可。

分析一下一个人 u 的胜利路径，大概可以拆分成 u 到在 l（满足 a_u\geq l）的点 v 使得要么他是擂主，要么擂主失败，以及 v 到根的路径满足每一步均不是擂主且擂主失败。

考虑到合法的 v 均在一条链上，枚举它在子树内树形 dp 即可。

具体来说，我们如何计算一个最大的时刻使得一个子树内的胜者的权值小于其父亲的深度？考虑到每个点 u 的子树的胜者的权值要么一定可以在 [\operatorname{depth}(u),2^{31}) 上任取，要么一定是 n 时刻时该子树的胜者的权值。

所以预处理出 n 时刻每个子树的胜者以及使得子树胜者固定的最小时刻即可。

综上，时间复杂度为 O(T n)，洛谷上可能略微卡常，我最终通过的代码加了快读快写以及循环展开才过的。具体实现可以参考我的代码对照下。