Disjoint Set Connected Components With Weighted Graph
Using arrays instead of classes and objects would make it easier for you to implement the disjoint set union concept.

Here's a resource to start off with:- Disjoint Set Union

for edge in edges:
    if find_set(edge[0], node_map) != find_set(edge[1], node_map):
        unioned_set = union(edge[0], edge[1], node_map, sets_map)
        cost_map[edge[2]] = unioned_set.count - 1


cost_map[edge[2]] will not be equal to the size of resultant set after union - 1.

It will be equal to the product of size of two individual sets.

Over here,

for i in xrange(1, largest_cost+1):
    val = cost_map.get(i, 0)
    prefixed_cost_data[i] = prefixed_cost_data[i-1] + val


largest_cost can be &gt;10^9. Neither can you store an array of that size, nor can you execute a loop with 10^9 operations with a time limit of 1sec.

Try using binary search on the L R query.

If you implement disjoint union set with arrays and make the above corrections , then I believe the code should work.