Efficient computation of a vertex-partition for graphs A finite simple connected graph $\Gamma$ with vertices $V(\Gamma)$ has a 
partition of its vertices into (at most) two subsets defined as follows: 
Given a spanning tree $T\subset \Gamma$, chose a function 
$\varphi_T:V(\Gamma)\longrightarrow \lbrace \pm 1\rbrace$ such that 
$\varphi(s)\varphi(t)=-1$ if $s,t\in V(\Gamma)$ are adjacent vertices 
of $T$. The product $\psi=\prod_T\varphi_T$ over all spanning trees 
of $\Gamma$ is well defined up to a global sign and induces a partition 
$\psi^{-1}(1)\cup\psi^{-1}(-1)$ of $V(\Gamma)$.
Is there an efficient way for computing this partition for an arbitrary graph?
Remark: The best way I can think of for a general graph is to consider all 
partitions $A\cup B$ of $V(\Gamma)$ which induce a connected bipartite 
subgraph (obtained by removing all edges having either both endpoints 
in $A$ or in $B$) of odd complexity.
 A: As you note, for a bipartite graph you get either the bipartition or the trivial partition (according as the number of spanning trees is even or odd). Any edge whose removal (keeping its endpoints) disconnects the graph must be in every spanning tree. So its two ends will be in the same or opposite parts of the partition according as the total number of spanning trees is even or odd. So we may delete all these edges since the number of spanning trees for the given graph will be the same as the number of maximal spanning forests of the reduced graph.  The reduced graph has one or more connected components each without degree one vertices or bridges. Each of these components is either two connected or  has  one or more cutpoints separating it into maximal 2 connected components. If any of those 2 connected components has an even number of spanning trees then the  reduced graph gets the trivial partition. 
I think it might be more interesting to have each spanning tree vote if each pair of vertices are "the same" or "opposite" (so "neutral" is a possible outcome)
A: This is effectively creating the bipartite coloring of a graph $G=(V,E)$, if it is bipartite.  There can be no bipartite coloring if there are odd length cycles in the graph which you are considering.
You can check to see if a graph is bipartite in $O(|V|\cdot |E|)$, i.e. time proportional to the product of the number of edges and vertices.
If your graph is a single component connected finite graph, start by pick any vertex as a starting point and assign it the distance $0$ (or equivalently the label $(-1)$.  Then iterate the following two steps alternately until every vertex is labeled, or until you end up attempting to assign two different labels to the same vertex (i.e. you find two different paths to the same vertex which are not the same length modulo $2$.


*

*follow every edge from your vertices labeled $0$ to get the next set of vertices and see if any of them are already labeled $0$, if there are then no such bipartition exists. If not, label them with the distance $1$ or alternately $(+1)$

*follow every edge from the vertices labeled $1$ to get the next set of vertices and see if any of them are already labeled $1$, if there are then no such bipartition exists.  If not, label them $0$ and continue to iterate.
If you end up attempting to label the same vertex with both labels/colors, then the graph is not bipartite.  Otherwise, you end up with every vertex labeled with the parity ($0$=even, $1$=odd) of their distance from the initial vertex chosen for this labeling.
