自动搬运

查看原文

来自洛谷，原作者为

	_2022gdgzby01 小粉兔，粉又粉，两只耳朵拎起来，割完动脉割静脉，一动不动真可爱，扒了皮，剁了块，放在锅里炒个菜，加上水，盖上盖，出锅之前撒香菜，端个碗，拿双筷，张起嘴来尝一块，盐不咸，味不淡，真是美味下酒菜。

搬运于2025-08-24 21:45:23，当前版本为作者最后更新于2024-11-06 13:32:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑容斥，枚举哪些串必然出现，那么贡献为 $(-1)^{选中的串数}$。

设 $f_{i,j}$ 表示 $i$ 的子树内，$i$ 点往上是 $j$ 这个串的贡献之和，那么总状态数为 $O(n+m)$ ，用 map 存储 $f$。

将子树的 DP 值与父亲合并时，按串长分类讨论：

若子树串比较长，那么暴力枚举它的前缀状态转移即可。

若父亲串比较长，那么一个子树状态对父亲状态的贡献编码后对应一个区间。

扫描线处理区间，对于相邻的区间内的所有 DP 值整体乘上一个数，线段树维护。

最后沿着线段树上有效节点走，即可不重不漏地得到所有新的状态。

时间复杂度 $O(n\log n)$。