SPOJ-HOLI problem

I did the question using the approach shown in the video but was not able to solve the problem ,


Question link:https://www.spoj.com/problems/HOLI/

Hi Dhiraj

This problem can be solved if its viewed from the edges point of view, rather than nodes point of view. We can easily observe that to obtain the maximum distance travelled by all the visitors, each edge should be travelled by maximum possible number of visitors. So the idea is since the maximum visitors which can travel the edge is minimum of the total number of nodes to the left and right of the edge, hence we compute it using DFS. If number of visitors one side of the edge is a, then the number of visitors on the other side of the edge automatically becomes n-a.

I have implemented the same idea, you can refer https://ide.codingblocks.com/s/84488

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.