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$.