We have given tree with $N$ nodes and $N-1$ edges, such that each edges is assigned positive weight. We need to find path of length between $L$ and $R$ inclusively, with maximum cost. Cost of a path is defined as a median of all costs of edges that lie on the path.

Let's define two types of costs of path between two nodes $i$ and $j$.

Cost 1: The number of edges on the path between $i$ and $j$.

Cost 2: We create array of all costs on edges on path between $i$ and $j$, then the cost is the median of this array. (In case of even number of elements we consider the median to be the bigger of the two middle elements).

Note that we don't need to know the starting and ending nodes in the best path, just its median.

For example:

N = 6, L = 3, R = 4
1 2 1
2 3 1
3 4 1
4 5 2
5 6 2
The best possible path is 2 -> 3 -> 4 -> 5 -> 6. 
It is valid in terms of cost 1, the number of edges is 4, which is between L and R.
And in terms of cost 2 the costs of edges are {1, 1, 2, 2}, and the median in this array is 2, which is maximum possible.
Another valid path is 2 -> 3 -> 4 -> 5, but the median of costs of edges is 1, which is not maximum possible.

I have a solution in $O(N^2 \log N)$ that tries every possible path and saves the costs of edges in binary search tree, but is is possible to get faster solution?

  • 1
    $\begingroup$ I do not undestand what are L and R. Can you give an example on a small tree. By the way, in a tree, there is a unique single path between each pair of nodes. $\endgroup$ – Optidad Apr 8 '19 at 18:42
  • $\begingroup$ Yes, let's say we are analysing path between i and j. This path can be analysed if the number of edges between them is number in the range [L,R] and the cost of the path is the median of costs of all edges on the path in the tree $\endgroup$ – someone12321 Apr 8 '19 at 18:45
  • $\begingroup$ Ok, to be clearer, you should say that we look for these two nodes $i$ and $j$. $\endgroup$ – Optidad Apr 8 '19 at 20:42
  • $\begingroup$ I also agree, the choice of words is not the best. Could you edit the question addressing what Vince said and maybe include a small example? Is the tree always binary? $\endgroup$ – ryan Apr 9 '19 at 0:56
  • $\begingroup$ I added one example, and the tree doesn't have to be binary, it can be arbitrary. I hope it is more clear what I'm asking now. $\endgroup$ – someone12321 Apr 9 '19 at 6:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.