5
Interesting problem involving tree with weighted nodes
source link: http://codeforces.com/blog/entry/107687
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK