Count bridging edges in a family of two component forests
I have an idea that will efficiently get you "halfway there". Hopefully you or someone else can think of a way to extend this to get the "other half" efficiently.

For a given edge $uv$ in $T$, let me rename the two subtrees that deleting $uv$ would create as $F_u^{uv}$ (this is the subtree containing $u$) and $F_v^{uv}$ (the one containing $v$). Denote by $E_u^{uv}$ the subset of $E$ for which both vertices belong to the vertex set of $F_u^{uv}$ (i.e., the graph edges that are "completely within" the $u$-subtree of $F$), and similarly for $E_v^{uv}$.

For each edge $uv$ in $T$, if we can efficiently compute both $|E_u^{uv}|$ and $|E_v^{uv}|$ , then we can compute $c(uv)$ simply by subtracting these two counts from the total number $|E|$ of edges.

Half of the necessary counts can be computed in $O(|E|)$ time as follows:


Root $T$ arbitrarily and consider all edges to be directed "down", away from the root.
Preprocess $T$ for fast lowest common ancestor (LCA) queries.
For each graph edge $uv$:


Increment a counter $\Delta_x$, where $x$ is the LCA of $u$ and $v$ in $T$.

Compute $|E_v^{uv}|$ as $\Delta_v + \sum_{c:vc\in T}|E_c^{vc}|$ for each $T$-edge $uv$ using a single postorder DFS traversal (here $u$ is the unique parent of $v$ in $T$).


Since LCA can be computed in constant time after linear preprocessing, the above takes only $O(|E|)$ time and space to compute all $n-1$ of the $|E_v^{uv}|$ values. (I think of $|E_v^{uv}|$ as the number of edges "completely below" $uv$.) But it does not compute any of the $n-1$ $|E_u^{uv}|$ values -- the numbers of edges "completely above" $uv$ -- and I can't think of an efficient way to do so.

You can of course reroot $T$ at a different vertex and repeat the exercise: The directions of some edges will be reversed, and the $|E_v^{uv}|$ values computed for each of them can be used for the $|E_u^{uv}|$ values in the original rooting. You could repeat this until all edges have been covered in both directions -- if you were lucky enough to be given a $T$ that is a Hamiltonian path, just 2 rootings would suffice, but in general "covering" all edges this way could require as many as $n-1$ rootings (think of a star tree), which leaves us no better off than the original method.

Ideas anyone?