[COCI] lattice (dichotomy + tree divide and conquer + string hash)

The question ：

Given a tree $n$ A tree of nodes , Each node has a lowercase letter $a—z$. Require the longest simple path , The string obtained along the path is a palindrome string .
（$1\le n\le 10^5$）

Ideas ：

The first thing to consider is , How to judge whether a path on the tree is a palindrome string .

The method used here is String hash .
for instance , to $a—z$ Each letter has its own （ My life depend on myself not the fate ） Set a hash value , Set up another $base$ Value and modulus $M$, character string $abbcbba$ The hash value of is $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)$.

that , After processing the prefix hash value , You can quickly calculate the hash value of the substring .
Determine whether a string is a palindrome string , We just need to get the hash value from the front to the back and the hash value from the back to the front , Compare whether they are the same .
So many times to ask whether a certain paragraph string is a palindrome string , We just preprocess the hash prefix from the front to the back , And the hash suffix from back to front . You can quickly calculate the hash values of a certain section from front to back and back to front for comparison , To determine whether it is a palindrome string .

With this tool , For this problem, we just need to preprocess the hash value on the tree , You can determine whether the path is a palindrome string through calculation .

 
Now? , Let's think about how to find the longest palindrome path . This is obviously satisfying Two points nature . therefore , The length of our binary path , Then determine whether there is a palindrome path of this length .

 
that , Now there is only one last question , Is how to check whether there is a palindrome path of a certain length .
Let's set the root to $R$, So there are two paths , One is through $R$ Of , One is not through $R$ Of .
Suppose we can $o(n)$ Calculate the course $R$ The situation of , For those who do not go through $R$ The situation of , Paths are in its subtree . So we can use Center of gravity decomposition , That is to say The trees divide To solve the , Just take the center of gravity as $R$, The overall complexity is $o(nlogn)$.

therefore , The last problem we need to solve now is , how $o(n)$ Check for the presence of tree roots $R$, And the palindrome path with a given length .
For a passage $R$ The path of , It must look like this .（ Solve the problem of stealing pictures ）

Determine whether this path is a palindrome string , We just have to judge $R$ To $C$ It's a palindrome string , also $C$ To $A$ String sum of $R$ To $C$ The same string .
We enumerate $A$ Settle down , Now $C$ It can also be calculated , We have judged $RC$, Work out $CA$, Just look in other subtrees , Whether there is $RB$ The value of and $CA$ identical . We put the other subtrees $RB$ Value saved to $set$ in , Can $o(logn)$ look for .
When we use $unordered\_set$ When , It becomes $o(1)$ Look for it. . So the complexity becomes $o(n)$ 了 .

 
Last , The overall complexity is $o(nlo{g}^{2}n)$ 了 .

Code ：

COO for a while .