回文树是个很神奇的数据结构。
这道题需要用到回文树这个数据结构。
这篇博文只介绍回文树。
回文树的节点表示一个回文串。
首先我们知道，回文串分长度为偶数和奇数两种。
回文树上必定有长度为$0$与$1$的节点。但是为了方便，我们把所有长度为$1$的节点挂在一个”长度”为$-1$的节点下，就可以像其它的节点一样处理。
与AC自动机一样，回文树的节点也有$fail$指针。每个节点的$fail$指向其最长回文后缀。
构建回文树的方式是一直向当前串的末尾添加字符。
假设当前串的最长回文后缀在回文树上的节点是$u$，将要添加的字符是$c$，则查看$u$前面一个字母是否是$c$，如果不是则找$u$的$fail$，不行再找，直到$u$前一个字母为$c$为止，就将$u$与新建的这个节点连边，并更新这个节点的$fail$为$u$的$fail$一直找$fail$直到其前第一个字母为$c$，走$c$的边之后的节点。
然后就要证为什么只新建一个节点了。
假设添加这个字符后有两个新的回文串$S[l_1\dots i]$和$S[l_2\dots i]$，$l_1<l_2$，那么根据回文串的性质，$S[l_1\dots l_1-l_2+i]=S[l_2\dots i]$。所以其实只新增了一个回文串。