An interesting Problem on tree

Revision en2, by _Ash__, 2018-08-12 19:26:29

There is a problem from phuket regional 2015 that i have been trying to solve.

Here is the problem link : https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=690&page=show_problem&problem=5321

The problem transforms into something like this , there is a tree ( at most 10^5 nodes) where each node has two values(let them call a,b). Now there are some (at most 10^5) queries of form : U V x y .

You have to find all the nodes on path U to V for which a*x + b*y is minimum. Note that if this minimum occurs for several nodes , you have to find them all. It is guaranteed that you don't have to print more than 3*10^5 nodes' id.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English _Ash__ 2018-08-12 19:26:29 4 Tiny change: 'e to find the all the n' -> 'e to find all the n'
en1 English _Ash__ 2018-08-12 19:21:10 706 Initial revision (published)