考试的时候do big die去刷bzoj.大概下午会hug zero.
sam的第二题.其实这个玩意是应该用sa做的,不过现在我觉得sa没有sam简单.虽然sam的构造和性质还是一团大雾.
这个题可以做出原串的后缀树,然后在上面dp一下.每个点对答案的贡献为任意两个不在同一子树的终态对数*深度.
然后倒过来建sam,它的parent树就是原串的后缀树.虽然我还没有成功理解这个东西.
然后坑了一会的一件事情是新建的nq节点的right集合为空.因为它只是一个扩展点,但是不是一个接受态ovo
我还是太弱啊怎么办.