DwivediAyush's blog

By DwivediAyush, history, 2 months ago,

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.

• 0

 » 2 months ago, # |   0 Any link?
•  » » 2 months ago, # ^ |   0 Omg Big fan.
 » 2 months ago, # | ← Rev. 2 →   0 I think answer is just cost of diameter — min(terminal_node_of_diameter[1],terminal_code_of_diameter[2]);I am not sure though.
•  » » 2 months ago, # ^ |   0 Ok its wrong I just found a counter case :clownglasses:.
 » 2 months ago, # |   0 But even if all costs are equal to $1$ it is the Hamiltonian path problem, isn't it?
 » 2 months ago, # |   +3 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.