C ++中树中两个不相交的路径的最大乘积

在本教程中，我们将讨论一个程序，以查找树中两个不相交的路径的最大乘积。

为此，我们将提供一个具有n个节点的无向树。我们的任务是在树中找到两条路径，以使它们的乘积最大且不相交。

示例

#include <bits/stdc++.h>
using namespace std;
//返回最大长度路径
int dfs(vector<int> g[], int& curMax, int u, int v) {
   int max1 = 0, max2 = 0, total = 0;
   for (int i = 0; i < g[u].size(); i++) {
      if (g[u][i] == v)
         continue;
      total = max(total, dfs(g, curMax, g[u][i], u));
      if (curMax > max1) {
         max2 = max1;
         max1 = curMax;
      }
      else
         max2 = max(max2, curMax);
      }
      total = max(total, max1 + max2);
      curMax = max1 + 1;
      return total;
   }
   //返回非相交路径的乘积
   int maxProductOfTwoPaths(vector<int> g[], int N) {
      int res = INT_MIN;
      int path1, path2;
      for (int i = 0; i < N; i++) {
         for (int j = 0; j < g[i].size(); j++) {
            int curMax = 0;
            path1 = dfs(g, curMax, g[i][j], i);
            curMax = 0;
            path2 = dfs(g, curMax, i, g[i][j]);
            res = max(res, path1 * path2);
         }
      }
      return res;
   }
   void addEdge(vector<int> g[], int u, int v) {
      g[u].push_back(v);
      g[v].push_back(u);
   }
}
int main() {
   int edges[][2] = {{1, 8}, {2, 6}, {3, 1},{5, 3}, {7, 8}, {8, 4},{8, 6} };
   int N = sizeof(edges)/sizeof(edges[0]);
   vector<int> g[N + 2];
   for (int i = 0; i < N; i++)
      addEdge(g, edges[i][0], edges[i][1]);
   cout << maxProductOfTwoPaths(g, N) << endl;
   return 0;
}

输出结果

6