You are given a tree with n vertices (1,2,...,n) and each vertex has a cost associated to it given by cost[1],..., cost [n] Among all possible paths which start at u and ends at v, for any (u,v) from 1 to n, in which each vertex occurs at most once, find the cost of the path for which the value of the expression "cost of path — min(cost[u],cost[v])" is maximised.
Eg: N=3 Cost[] = {3,1,2} Edges are (1,2) and (1,3)
Answer would be 5, which is the cost of the path 2--1--3.
Any link?
But even if all costs are equal to $$$1$$$ it is the Hamiltonian path problem, isn't it?
I will assume $$$cost[i] \geq 0$$$ and $$$n \geq 3$$$. In this case the $$$u$$$ and $$$v$$$ will be both leafs of the tree.
First root the tree in any vertex that is not a leaf. Defining the answer as
$$$max( dis[u][v] - min(cost[u],cost[v]))1 \leq u < v \leq n$$$, $$$u$$$ and $$$v$$$ are leafs.
This is the same to:
$$$max (dis[u][v] - cost[u]), 1 \leq u \leq n, \ 1 \leq v \leq n$$$. $$$u$$$ and $$$v$$$ are leafs.
Since $$$u$$$ is a leaf, we can change the formula to:
$$$max (dis[w][v]), 1 \leq w \leq n, \ 1 \leq v \leq n$$$, $$$v$$$ is a leaf, there is a child $$$u$$$ of $$$w$$$ that is a leaf and $$$u \neq v$$$.
Define $$$S$$$ the set of vertex that of one of it's childs is a leaf.
With this, we can store the values:
$$$dp_0[v]$$$ = the maximum path from $$$v$$$ to one leaf in it subtree;
$$$dp_1[v]$$$ = the maximum path from $$$v$$$ to one vertex $$$w \in S$$$ and $$$w$$$ is in subtree of $$$v$$$.
With this we can solve the problem.
For the case where we allow $$$cost[i] < 0$$$. Looks like we can solve it using centroid decomposition.