SPOJ :: KOICOST

Problem Link

The Problem in Short:

Given an undirected weighted graph.
There is a function Cost(u,v), which is defined as follows:
While there is a path between vertex u and v, delete the edge with the smallest weight. Cost(u,v) is the sum of the weights of the edges that were deleted in this process.
your task is to calculate the sum of Cost(u,v) for all pairs of vertices u and v, where u < v

The Solution:

To describe the solution we'll need a few notations:

bound(x,y) = the last edge, that has to be deleted if we want to disconnect vertex x and y by the process described in the problem statement.
f(u,v) = number of pair of vertices (x,y) such that, bound(x,y) = edge (u,v)
w(u,v) = weight of the edge (u,v)
csum(u,v) = cumulative sum of weights of all edge (u',v') such that w(u',v') <= w(u,v)

so, result = sum over ( csum(u,v)*f(u,v) ) for all edge (u,v)


Now, the problem is to calculate f(u,v) efficiently.

Consider the following process which is the reverse of the process described in the problem statement.

Lets assume that, initially all the vertices are disconnected. We add the edges one by one in the decreasing order of their weights.

define, g(u,v) = the number of pair of vertices (x,y) such that, (x,y) becomes connected when we add the edge (u,v) in the reverse process.

Note that, f(u,v) = g(u,v) (the proof is left to the reader)

Here is the algorithm that calculates g(u,v) for all the edges.

1. sort all the edges in the decreasing order of their weights
2. create a disjoint set of for all the nodes. (yes, we'll need the disjoint-set data structure)
3. in the root of each disjoint set, store the size of that set.
let's denote by sz(u), the size of the disjoint set that vertex u is in.

4. For each edge (u,v):

if u and v are connected already (i.e. in the same set)
f(u,v) = g(u,v) = 0
else:
f(u,v) = g(u,v) = sz(u) * sz(v)
result = result + f(u,v)*csum(u,v)
disjoint_set_union(u,v)