[COCI]Lampice (二分+树分治+字符串哈希)

题意：

给定一棵$n$个结点的树，每个结点有一个小写字母$a—z$。要求一条最长的简单路径，满足沿路径得到的字符串是回文串。
（$1\le n\le 10^5$）

思路：

首先要考虑的问题是，用什么方式去判断树上的一条路径是不是回文串。

这里采用的方法是字符串哈希。
举个例子，给$a—z$每个字母都自己（我命由我不由天）设置一个哈希值，再设置一个$base$值和模数$M$，字符串$abbcbba$的哈希值就是$H(a)+H(b)\times base+H(b)\times bas{e}^2+H(c)\times bas{e}^3+\dots +H(a)\times bas{e}^6(modM)$。

那么，处理出前缀哈希值后，可以快速算出子串的哈希值。
判断一个串是不是回文串，我们只要得到从前往后的哈希值和从后往前的哈希值，比较是否相同即可。
那么多次询问某段子串是不是回文串，我们只要预处理出从前往后的哈希值前缀，和从后往前的哈希值后缀。就可以快速算出某段前往后和后往前的哈希值进行比较，来判断是否是回文串。

有了这个工具后，这题我们只要在树上预处理出哈希值，就可以通过计算判断路径是否为回文串。

 
现在，我们再来思考怎么求最长的回文路径。这个显然满足二分性质。所以，我们二分路径的长度，然后判断是否存在该长度的回文路径。

 
那么，现在就剩最后一个问题，就是怎么检验是否存在某个长度的回文路径。
我们设根为$R$，那么路径分两种，一种是经过$R$的，一种是不经过$R$的。
假设我们可以$o(n)$算出经过$R$的情况，对于不经过$R$的情况，路径都是在它的子树里。于是我们就可以用重心分解，也就是树分治来解决了，只要每次拿重心作为$R$，总体复杂度就是$o(nlogn)$。

所以，我们现在最后要解决的问题就是，如何$o(n)$检验是否存在经过树根$R$，且长度给定的回文路径。
对于某一条经过$R$的路径，一定是长这样子的。（题解盗图）

判断这条路径是否是回文串，我们只要判断$R$到$C$是回文串，并且$C$到$A$的串和$R$到$C$的串相同。
我们通过枚举把$A$定下来，这时候$C$也能算出来，我们判断完$RC$，算出$CA$，就只要看其他子树里，是否存在$RB$的值和$CA$相同。 我们把其他的子树的$RB$值存到$set$里，就可以$o(logn)$找。
当我们用$unordered\_set$的时候，就变成$o(1)$找了。那么复杂度就变成$o(n)$了。

 
最后，总体复杂度就是$o(nlo{g}^{2}n)$了。

代码：

咕一会儿。