java - 查找具有子路径且具有最大gcd(起始节点，结束节点)的路径

Question

我在一场竞赛中遇到了一个问题(竞赛已于几周前结束)。我解释的问题是 -:

Given an undirected acyclic graph which is connected by (N-1) edges and N nodes. The graph is guaranteed to be connected. Given two nodes u and v, you have to find two nodes x and y of the graph such that the path between these two nodes overlaps the path between the given cities u and v completely and gcd(x, y) is maximum possible.

约束

1 <= N <= 5 * 10^5

1 <= a,b,u,v <= N

其中 a,b 是图中的两个任意节点。

示例让图表有 10 个节点(1 到 10)

现在，在前一行中，我将给出两个整数 a 和 b，这意味着 a 和 b 直接相连。

1 4

1 5

1 2

4 3

4 6

5 7

2 10

2 9

2 8

最后紫外线4 2

答案 - 4

从 u 到 v 的路径是 4 -> 1 -> 2

现在，与从 u 到 v 的路径完全重叠的一些路径是:

4 -> 1 -> 2 -> 10

3 -> 4 -> 1 -> 2 -> 9

4 -> 1 -> 2 -> 8

等等......

请注意，选择从 4 到 8 的路径与路径 u 到 v 完全重叠，并且 gcd(4,8) = 4 这是可能的最大值。

图表是: /image/Phkwi.png 时间限制:3.0秒

我解决问题的方法是:

找到从每个节点到其他每个节点的路径并将其存储在数组列表中。

迭代所有列表并查找数组中是否包含 u 和 v 路径。

如果找到路径，则计算起始节点和结束节点的gcd，并检查最大gcd。

但是我认为我的方法太暴力，代码太长，而且我认为它太复杂了。

有人可以建议任何建议或方法来解决这个问题吗？

Answer 1

也许您可以在起始和结束顶点上执行 dfs，然后从这些顶点中删除子图上已有的顶点。现在您拥有了所有可能的顶点，它们可以成为解决方案的一部分。检查这些顶点的所有可能组合，并选择具有最大 gcd 的对。在 dfs 期间，请确保添加一个 if 条件来忽略与其相关的顶点，以便在子路径的每一侧您只能获得不属于子路径的顶点