Finding appropriate spanning tree of connected bipartite graph
Isn't this a special case of matroid intersection,
which is solvable in polynomial time?

Fix your graph $G$ and any integer $d \in \{0,1,\ldots,\max_i a_i\}$.
You want to maximize $d$; you can try all possibilities.
For a given $d$, you want to answer the following question:


  Is there is a spanning tree $T$ such that $\max_i a_i - \mbox{deg}_T(u_i) \le d$?


Since any spanning tree has $n-1$ edges, the following question is equivalent:


  Is there an edge-set $S$ of size at least $|E|-n+1$, with at most $d$ edges incident to each vertex in $U$, whose complement contains a spanning tree?


Thus, your problem reduces to the following problem:


  Find a maximum-size edge-set $S$ having at most $d$ edges incident to each vertex in $U$ and whose complement contains a spanning tree.


The independent sets of edges in $G$ form a matroid.  The bases are the spanning trees.  The dual of this matroid is a matroid $M_t^*$.  The edge-sets in $M_t^*$ are the edge-sets whose complement contains a spanning tree.

The edge-sets in which each vertex $u_i$ in $U$ has degree at most $d$ form yet another matroid $M_d$. 

Thus, the following two conditions on edge-set $S$ are equivalent:


$S$ is in the intersection $M_d \cap M_t^*$ of the two matroids;
$S$ has at most $d$ edges incident to each vertex in $U$, and the complement of $S$ contains a spanning tree.


So the following algorithm solves the problem in polynomial time:


  Using matroid intersection, find a maximum-size edge-set $S$ in $M_d \cap M^*_t$.