algorithm - 树中的两个节点不相交路径，使得这些长度的乘积最大

Question

我想在一棵有n个节点的树中找到两条路径，使得这两条路径没有任何公共(public)节点并且这两条路径的长度相乘得到最大值。任何人都可以帮助我如何解决这个问题？

Answer 1

首先，使用递归过程生成每个可能的唯一路径的列表。

你最终有 m 条可能的路径。

其次，设置一个包含 m x m 个元素的数组。

检查 m 条路径中的每条路径与所有其他 m-1 条路径，并将相应长度的乘积存储到数组中。这样做检查两条路径是否有共同的节点。如果是，则存储 0。

第三，检查 m x m 数组中具有最大值的元素。

你还能做什么？这是非常蛮力的，但如果没有更多关于树属性的信息，这是唯一的方法。