在无向无环图中找到最长回文路径的长度

Question

问题是：给定一个无向无环图（N个节点和N-1条边），其中每个节点都标有一个字符，求图中结点最长路径的长度，形成回文.

假设有 N (1 <= N <= 500 000) 个节点，有没有什么算法可以解决这个问题O(N^2) 或 O(N.log2(N))?

的时间复杂度

经过一些研究，我认为这可以用图上的 Manacher 算法解决

Answer 1

这个确切的问题，但有更严格的约束 (N ≤ 50 000)，出现在 COCI 2019/2020 第 3 轮（任务 Lampice）上。

这里是Tasks and Editorial，它描述了一个复杂度为O(N.log2(N)).

的解决方案