嘛回文。

先说说回文树。

Orz VictorWonder写的论文：http://victorwonder.blog.uoj.ac/blog/146

其实就是两棵树（分别代表奇偶长度的回文串）+回文后缀链咯，在线维护什么的不难玩

介绍的话上面的博文也写的很清楚了，想想应用？

论文里面说能把两个树合并到一起，就能动态化？弄个树形DP？弄个LCT？妈呀构造不出来。。。

自己后来又想了几个模型，在这里写不下就不写了。

int now, tmp, last=0;
cn=1; len[0]=0; len[1]=-1; fail[0]=fail[1]=1; last=0;
//Init
rep(i, 1, L)
{
	for(now=last; s[i-len[now]-1]!=s[i]; now=fail[now]);
	if (!c[now][s[i]-'a']) 
	{
		for(tmp=fail[now]; s[i-len[tmp]-1]!=s[i]; tmp=fail[tmp]);

		//New Node(Array_Fail Before Array_C)
		fail[++cn]=c[tmp][s[i]-'a'];
		c[now][s[i]-'a']=cn;

		//Cal Data
		len[cn]=len[now]+2; d[cn]=d[fail[cn]]+1;
	}
	last=c[now][s[i]-'a'];
	cnt[last]++;
}

几个应用：

清澄1280-BZOJ2565

清澄1255-BZOJ2160

清澄1393

HDU5421

对于回文子串，回文树能搞的Manacher也能搞，Manacher能搞的回文树有时也不行（在我这个蒟蒻看来的啊。。。

换句话说，有些题回文树很容易解决，Manacher却比较麻烦；有些题则颠倒过来

所以，Manacher其实也是要很熟练的。。。

rep(i, 0, l-1) s[i*2+1]='$', s[i*2+2]=c[i];
s[0]='#'; s[l*2+1]='$';
ans=o=p=0;
rep(i, 1, l*2+1)
{
	k[i] = i<p ? min(p-i, k[o*2-i]) : 1;
	while (s[i+k[i]] == s[i-k[i]]) k[i]++;
	if (i+k[i]>p) p=i+k[i], o=i;
}

然后就来看各种回文题了：

BZOJ2342 双倍回文

做出Manacher后，枚举中心和次中心，然后加个最优性剪枝可过

涉及论文：《回文树的构建及其应用》《浅谈回文子串问题》