I am given a (simple, undirected, connected) graph $ G = (V, E)$ and a fixed spanning tree $ T$ in this graph. Removing an edge $ e\in E(T)$ from $ T$ splits it into a spanning forest $ F^e$ with two components $ F_1^e$ and $ F_2^e$ . I am interested in the number $ c(e)$ of edges in $ G$ that connect $ F^e$ i.e. with one vertex in $ F_1^e$ and the other in $ F_2^e$ .

I would like to compute the number $ c(e)$ for all $ e$ in $ T$ simultaneously. This can be done naively in $ O(|V||E|)$ . Is there a faster way to achieve this?

The graphs I am working with are small-world graphs. In particular the average distance between nodes in $ G$ can be assumed to be small.