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

Question

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

假设有N (1 <= N <= 500 000)个节点，是否有任何算法可以解决这个问题，时间复杂度为O(N^2) 或 O(N.log2(N))？

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

标签： graph-theorygraph-algorithmpalindromeundirected-graph

Answer 1

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

这是Tasks and Discussions，它描述了一个复杂度为O(N.log2(N))的解决方案。