Given a weighted graph G=(V,E) design an algorithm to partition the edge set E into disjoint sets X and Y(E=X U Y) such that X comprises of all those edges which do not appear in any of the minimal spanning tree of the given graph G.
Construct any minimal spanning tree. The most expensive edge e(i,j) on the path between any 2 vertices i,j of the MST is well defined (the same for every MST) and can be found using sparse table (constructed like for LCA). For every edge connecting vertices i,j, check if its weight is at most e(i,j); iff it is, the edge can be in some MST.