树中最大产品非交叉路径

Question

问题：

给定一棵有 N 个节点的无向树 ( 2 <= N <= 100,000 ) and N-1 edges, how can I find two non-intersecting paths with maximum product?

示例：

6

1-2

2-3

2-4

5-4

6-4

答案：4

我需要找到 O(N) 的解决方案。我写了 O(n^2) 解决方案，但它不接受它。这是我的 O(n^2) 解决方案：

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    private static int currentMax;
    private static List<List<Integer>> tree;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new FileReader("src/input.txt"));
        int N = Integer.parseInt(reader.readLine()) - 1;
        int[][] edges = new int[N][2];
        tree = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            String[] line = reader.readLine().split(" ");
            edges[i][0] = Integer.parseInt(line[0]);
            edges[i][1] = Integer.parseInt(line[1]);
        }

        for(int i = 0; i < N + 2; i++)
            tree.add(i, new ArrayList<>());

        for (int[] edge : edges) {
            tree.get(edge[0]).add(edge[1]);
            tree.get(edge[1]).add(edge[0]);
        }

        long res = 0;
        int path1, path2;
        for(int i = 1; i < N + 2; i++) {
            for(int j = 0; j < tree.get(i).size(); j++) {
                currentMax = 0;
                path1 = dfs(tree.get(i).get(j), i);
                currentMax = 0;
                path2 = dfs(i, tree.get(i).get(j));
                res = Math.max(res, (long) path1 * path2);
            }
            System.out.println(i);
        }

        System.out.println(res);
        reader.close();
    }


    private static int dfs(int root, int visited) {
        int fisrtMax = 0, secMax = 0;
        int total = 0;
        for(int i = 0; i < tree.get(root).size(); i++) {
            if (tree.get(root).get(i) == visited)
                continue;
            total = Math.max(total, dfs(tree.get(root).get(i), root));
            if (currentMax > fisrtMax) {
                secMax = fisrtMax;
                fisrtMax = currentMax;
            } else if(currentMax > secMax)
                secMax = currentMax;
        }
        if (fisrtMax + secMax > total)
            total = fisrtMax + secMax;

        currentMax = fisrtMax + 1;
        return total;
    }
}

Answer 1

从您的代码中，我了解到您想要任何两个非顶点相交路径的最大长度乘积。

在 DFS 中，对于由边及其可能方向之一定义的每个子树（总共 2N 个子树），您只计算两个值：顶点到子树根的最大距离和顶点的最大长度子树中的路径，即它的直径。这是一个正确的想法，您只需要更有效地计算它们 - 您需要多次重新计算这些 O(N) 值。

简单的记忆就足够了。您可以使用 2N 对（最大距离、直径）的列表来实现它，其中一个对应边的每个端点，按照输入中给出的顺序排列。这里有一个巧妙的实现技巧：考虑如果

root

是这些值中的第 (2i+k) 个值（k = 0 或 1），那么

visited

是边 i 的另一个端点，即 (2i +1-k) 个值。你应该对所有东西使用这个“有向边索引” - 邻接图，

dfs()

的唯一参数，检查你是否试图以你来时的方式返回......并表示 dfs 输出的记忆。除了这些更改之外，您的代码原则上是正确的。