2022/04/12 做题记录

识别子串

可以容易用后缀自动机+双指针求出从每一位开始最少走几位能使这个串只出现过一次，发现每一位的答案只能是覆盖它的最短的串或者是离它左边最近的不覆盖它的串，写个线段树+前缀最大值就行。

code: /code/2022.4.12/bz1396.cpp

黑暗前的幻想乡

容斥，枚举钦定最多只用哪些建筑公司的边，然后矩阵树定理就行。

code: /code/2022.4.12/P4336.cpp

【CODECHEF】Children Trips

可以通过树上倍增求出从一个点走一天能走到哪，对于 $p > \sqrt{n}$ 直接暴力跳，而对于每一个 $p \le \sqrt{n}$ 我们预处理出从每个点跳 $2^n$ 天能跳到哪，查询时也树上倍增就行。

虽然从下往上跳和从上往下跳并不完全相同，但我们可以吧从下往上跳理解成“找到最往上的一个跳 x 步能到的点”，只要保证两边跳到最后剩的距离都大于等于 1 小于 p 就行，这样中间只可能需要跳 0/1/2 步，这样再结合上另一边 “找到最往上的一个跳 x 步能到的点” 就能证明答案时正确的。

code: /code/2022.4.12/TRIPS.cpp