树中两条不相交路径的最大乘积O(N)求解方案

给定一棵包含N个节点（2 ≤ N ≤ 100,000）和N-1条边的无向树，如何找到两条不相交路径，使得它们的路径长度乘积最大？

示例 #

• 节点数：6
• 边：1-2、2-3、2-4、5-4、6-4
• 答案：4

我需要一个O(N)时间复杂度的解决方案。我写的O(n²)代码没通过，代码如下：

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;
    }
}

O(N)时间复杂度解决方案 #

核心思路 #

要最大化两条不相交路径的乘积，本质是找到一种拆分方式，把树分成两个无交集的子结构，分别取这两个子结构的直径（子结构内的最长路径），计算乘积的最大值——最优的两条不相交路径必然是各自子结构里的最长路径，这样乘积才会最大。

实现依赖树的直径性质：

1. 先找到整棵树的直径（最长路径）及其两个端点；
2. 通过两次DFS预处理每个子树的直径和最长链；
3. 枚举每一条边，切断边后快速获取两个子树的直径，计算乘积并维护全局最大值。

具体步骤 #

1. 找树的直径：
   • 随机选一个节点，BFS/DFS找到最远节点u；
   • 从u出发，BFS/DFS找到最远节点v，u到v的路径就是树的直径；
2. 两次DFS收集子树信息：
   • 从u出发DFS，记录每个节点子树的直径subDiamU和子树内的最长链maxDepthU；
   • 从v出发DFS，记录每个节点子树的直径subDiamV和子树内的最长链maxDepthV；
3. 枚举边计算乘积：
   对每条边cur-next，切断后：
   • 一部分是next的子树，直径为subDiamU[next]；
   • 另一部分是剩余树结构，直径取subDiamV[cur]（剩余结构内的子树直径）和(原直径长度 - cur到u的距离) + maxDepthV[cur]（剩余结构内可能的新直径）的较大值；
     计算两者乘积，更新全局最大值。

Java代码实现 #

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

public class Main {
    static List<List<Integer>> tree;
    static int n;
    static int[] distU, distV;
    static int[] maxDepthU, subDiamU;
    static int[] maxDepthV, subDiamV;
    static long ans = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        tree = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            tree.add(new ArrayList<>());
        }
        for (int i = 0; i < n - 1; i++) {
            String[] parts = br.readLine().split(" ");
            int u = Integer.parseInt(parts[0]);
            int v = Integer.parseInt(parts[1]);
            tree.get(u).add(v);
            tree.get(v).add(u);
        }

        // 找直径的两个端点u和v
        int u = bfs(1);
        int v = bfs(u);

        // 从u出发DFS，记录子树深度和子树直径
        maxDepthU = new int[n + 1];
        subDiamU = new int[n + 1];
        dfsU(u, -1);

        // 从v出发DFS，记录子树深度和子树直径
        maxDepthV = new int[n + 1];
        subDiamV = new int[n + 1];
        dfsV(v, -1);

        // 枚举每条边，计算切断后的两个子树直径乘积
        dfsCalc(u, -1);

        System.out.println(ans);
    }

    // BFS找最远节点，同时记录距离
    static int bfs(int start) {
        int[] dist = new int[n + 1];
        Arrays.fill(dist, -1);
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        dist[start] = 0;
        int farNode = start;
        while (!q.isEmpty()) {
            int cur = q.poll();
            for (int next : tree.get(cur)) {
                if (dist[next] == -1) {
                    dist[next] = dist[cur] + 1;
                    q.add(next);
                    if (dist[next] > dist[farNode]) {
                        farNode = next;
                    }
                }
            }
        }
        if (start == 1) {
            distU = dist;
        } else {
            distV = dist;
        }
        return farNode;
    }

    // 从u出发的DFS，计算子树的最大深度和子树直径
    static void dfsU(int cur, int parent) {
        int first = 0, second = 0;
        subDiamU[cur] = 0;
        for (int next : tree.get(cur)) {
            if (next == parent) continue;
            dfsU(next, cur);
            // 更新子树直径：取当前值或子节点的子树直径
            subDiamU[cur] = Math.max(subDiamU[cur], subDiamU[next]);
            // 更新最长的两个链，用于计算当前子树的可能直径
            if (maxDepthU[next] + 1 > first) {
                second = first;
                first = maxDepthU[next] + 1;
            } else if (maxDepthU[next] + 1 > second) {
                second = maxDepthU[next] + 1;
            }
        }
        // 当前子树的直径也可能是两个最长链之和
        subDiamU[cur] = Math.max(subDiamU[cur], first + second);
        maxDepthU[cur] = first;
    }

    // 从v出发的DFS，计算子树的最大深度和子树直径
    static void dfsV(int cur, int parent) {
        int first = 0, second = 0;
        subDiamV[cur] = 0;
        for (int next : tree.get(cur)) {
            if (next == parent) continue;
            dfsV(next, cur);
            subDiamV[cur] = Math.max(subDiamV[cur], subDiamV[next]);
            if (maxDepthV[next] + 1 > first) {
                second = first;
                first = maxDepthV[next] + 1;
            } else if (maxDepthV[next] + 1 > second) {
                second = maxDepthV[next] + 1;
            }
        }
        subDiamV[cur] = Math.max(subDiamV[cur], first + second);
        maxDepthV[cur] = first;
    }

    // 枚举每条边，计算切断后的两个子树直径乘积
    static void dfsCalc(int cur, int parent) {
        for (int next : tree.get(cur)) {
            if (next == parent) continue;
            // 第一部分：next子树的直径
            long part1 = subDiamU[next];
            // 第二部分：剩余树结构的直径，取两个候选值的最大值
            long candidate1 = subDiamV[cur];
            long candidate2 = (distU[v] - distU[cur]) + maxDepthV[cur];
            long part2 = Math.max(candidate1, candidate2);
            // 更新全局最大值
            ans = Math.max(ans, part1 * part2);

            dfsCalc(next, cur);
        }
    }
}

复杂度说明 #

所有DFS/BFS操作都是线性的，每个节点和边仅被访问常数次，整体时间复杂度为O(N)，完全适配题目中1e5级别的数据规模。

内容的提问来源于stack exchange，提问作者Aibar