Maximum product of two non-intersecting paths in a tree - GeeksforGeeks
Given an undirected connected tree with N nodes (and N-1 edges), we need to find two paths in this tree such that they are non-intersecting and the product of their length is maximum.
Read full article from Maximum product of two non-intersecting paths in a tree - GeeksforGeeks
Given an undirected connected tree with N nodes (and N-1 edges), we need to find two paths in this tree such that they are non-intersecting and the product of their length is maximum.
We can solve this problem by depth first search of tree by proceeding as follows, Since tree is connected and paths are non-intersecting, If we take any pair of such paths there must be a third path, connecting these two and If we remove an edge from the third path then tree will be divided into two components — one containing the first path, and the other containing the second path. This observation suggests us the algorithm: iterate over the edges; for each edge remove it, find the length of the path in both connected components and multiply the lengths of these paths. The length of the path in a tree can be found by modified depth first search where we will call for maximum path at each neighbor and we will add two maximum lengths returned, which will be the maximum path length at subtree rooted at current node.
Implementation Details:
Input is a tree, but there is no specified root in it as we have only collection of edges. The tree is represented as undirected graph. We traverse adjacency list. For every edge, we find maximum length paths on both sides of it (after removing the edge). We keep track of maximum product caused by an edge removal.
Input is a tree, but there is no specified root in it as we have only collection of edges. The tree is represented as undirected graph. We traverse adjacency list. For every edge, we find maximum length paths on both sides of it (after removing the edge). We keep track of maximum product caused by an edge removal.
int
dfs(vector<
int
> g[],
int
& curMax,
int
u,
int
v)
{
// To find lengths of first and second maximum
// in subtrees. currMax is to store overall
// maximum.
int
max1 = 0, max2 = 0, total = 0;
// loop through all neighbors of u
for
(
int
i = 0; i < g[u].size(); i++)
{
// if neighbor is v, then skip it
if
(g[u][i] == v)
continue
;
// call recursively with current neighbor as root
total = max(total, dfs(g, curMax, g[u][i], u));
// get max from one side and update
if
(curMax > max1)
{
max2 = max1;
max1 = curMax;
}
else
max2 = max(max2, curMax);
}
// store total length by adding max
// and second max
total = max(total, max1 + max2);
// update current max by adding 1, i.e.
// current node is included
curMax = max1 + 1;
return
total;
}
// method returns maximum product of length of
// two non-intersecting paths
int
maxProductOfTwoPaths(vector<
int
> g[],
int
N)
{
int
res = INT_MIN;
int
path1, path2;
// one by one removing all edges and calling
// dfs on both subtrees
for
(
int
i = 0; i < N; i++)
{
for
(
int
j = 0; j < g[i].size(); j++)
{
// calling dfs on subtree rooted at
// g[i][j], excluding edge from g[i][j]
// to i.
int
curMax = 0;
path1 = dfs(g, curMax, g[i][j], i);
// calling dfs on subtree rooted at
// i, edge from i to g[i][j]
curMax = 0;
path2 = dfs(g, curMax, i, g[i][j]);
res = max(res, path1 * path2);
}
}
return
res;
}