Problem Link

My code link

My idea:

*I made a graph providing connection to every node to all other nodes.

*Distance = sqrt( (x1 — x2 )^2 + ( y1 — y2 )^2 )

*Ran MST( Minimum Spanning Tree ) & saved the summation of costs.

*Made a graph from the MST.

*Made a Sparse Table using the MST graph & also saved the weight of maximum weighted edge for the paths.

*Then I tried to make a magical road between every possible node & searched for possible maximum ( A/B ) value, for delete a edge, I took help of the LCA for finding the maximum weighted edge between the path of currently two working nodes.

***I've been trying this problem for several days, but can't find any problem. Please help If anyone have free time.

Thanks in advance.

UPDATE: Got Accepted. { The Mistake was in Minimum Spanning Tree. Thank you. }