Problem: http://opc.iarcs.org.in/index.php/problems/HISPDNET
Solution: http://hastebin.com/dawawokivo.avrasm
I used Kruskal’s algo to find the minimum spanning tree from the vertices 2 to N. Yet, it’s leading to a TLE. What am I missing?
I suspect that TLE is caused by using iostream. In worst case, this probrem has 4*10^6 integers as input . You use ‘ios_base::sync_with_stdio(false);’ . But ‘scanf’ is faster than. Try using ‘scanf’ for input.
(You may feel this answer is hard to read. Because I am not good at English. Sorry.I wish you good luck.)
I used ios_base::sync_with_stdio(false) along with cin.tie(NULL) which should make it even faster, but it’s still leading to a TLE in almost all the test cases. That probably means there is a problem with the logic or some part of the logic in the code, or it’s even leading to an infinite loop somewhere. Thanks anyway. Oh, and I had no trouble reading your answer 
I find another problem.You use union-find tree in Kruscal’s algo.
In this data structure,
init:O(n)
union:O(H)
find:O(H)
(H is tree’s height)
I look like your tree’s height is O(N) in worst case. From this, your program is O(N^3). But,two methods union and find are possible to fast,because the height of union-find tree by using two techniques is O(α(n)).
Details on how: https://en.wikipedia.org/wiki/Disjoint-set_data_structure
I wish you good luck.