The problem is: given an undirected acyclic graph (N nodes and N-1 edges), where each node is labeled with a character, find the length of the longest path of nodes in the graph that forms a palindrome.
Suppose there are N (1 <= N <= 500 000) nodes, is there any algorithm to solve this problem with the time complexity of O(N^2) or O(N.log2(N))?
After some research, I think this might be solved with Manacher Algorithm on a graph
this exact problem, but with tighter constraints (N ≤ 50 000), appeared on COCI 2019/2020, Round 3 (task Lampice).
here is Tasks and Editorial, it describes a solution with complexity O(N.log2(N)).