Tích lớn nhất hai đường không giao nhau trong cây trong C++

Mô tả bài toán

Cho cây không hướng liên thông n nút. Tìm 2 đường không giao nhau (không chung đỉnh) sao cho tích độ dài 2 đường lớn nhất.

Ví dụ: Cây có đường C-A-B (độ dài 2) và F-E-D-G-H (độ dài 4) → Tích = 8.

Giải pháp (DFS trên cây)

• Với mỗi cạnh (u,v), coi như cắt cây thành 2 thành phần.
• Tìm đường dài nhất (đường kính) trong mỗi thành phần bằng DFS.
• Tính tích 2 độ dài đường kính, lấy max trên tất cả cạnh.

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

int TreeTraverse(vector<int> graph[], int& currPathMax, int val1, int val2) {
    int max1 = 0, max2 = 0, maxVal = 0;
    for (int v : graph[val1]) {
        if (v == val2) continue;
        maxVal = max(maxVal, TreeTraverse(graph, currPathMax, v, val1));
        if (currPathMax > max1) { max2 = max1; max1 = currPathMax; }
        else max2 = max(max2, currPathMax);
    }
    maxVal = max(maxVal, max1 + max2);
    currPathMax = max1 + 1;
    return maxVal;
}

int FindMaxProductPath(vector<int> graph[], int Size) {
    int maxProd = -10;
    for (int i = 0; i < Size; i++) {
        for (int j = 0; j < graph[i].size(); j++) {
            int currPathMax = 0;
            int pathA = TreeTraverse(graph, currPathMax, graph[i][j], i);
            currPathMax = 0;
            int pathB = TreeTraverse(graph, currPathMax, i, graph[i][j]);
            maxProd = max(maxProd, pathA * pathB);
        }
    }
    return maxProd;
}

void insertEdge(vector<int> graph[], int u, int v) {
    graph[u].push_back(v);
    graph[v].push_back(u);
}

int main() {
    int Size = 8;
    vector<int> graph[Size + 2];
    insertEdge(graph, 1, 2);
    insertEdge(graph, 2, 4);
    insertEdge(graph, 3, 1);
    insertEdge(graph, 5, 4);
    insertEdge(graph, 7, 8);
    insertEdge(graph, 8, 4);
    insertEdge(graph, 5, 6);
    cout << "Maximum product of two non-intersecting paths of tree is " << FindMaxProductPath(graph, Size) << "\n";
    return 0;
}

Đầu ra

Maximum product of two non-intersecting paths of tree is 8