DwivediAyush's blog

By DwivediAyush, history, 18 months ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any link?

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

But even if all costs are equal to $$$1$$$ it is the Hamiltonian path problem, isn't it?

»
18 months ago, # |
  Vote: I like it +3 Vote: I do not like 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.