假期做的串串

这个假期好像还是做了点能写出来的题的。

首先肯定要建出来 AC 自动机，发现答案具有二分性，这个第 k 大看起来就不太好直接做，考虑上一个二分，但是现在还是不好求，因为我们的 $cnt_i$ 是不同的。

那么怎么能让 $cnt_i$ 相同呢？现在就出来了最 👍 的一步，我们把这个串在 AC 自动机上跑到过的点全部拉出来建一颗虚树（建的是 fail 树的虚树），然后就惊奇的发现虚树上每条边的 $cnt$ 是相同的 😮，现在我们只要在原树上建一颗主席树，当前节点的主席树从 fail 树父亲继承过来，对虚树上的每条边在原树上进行二分，即求 $v_i \ge \lceil \frac{mid}{cnt_i} \rceil$ 就行了，因为 $cnt$ 都相同，所以可以随便做，时间复杂度 $O(n\ log^2 n)$