Let $T_{n}$ be the number of trees on $[n]$. Explain the identity below in terms of $T_{n}$ and prove it.
$2(n-1)n^{n-2}=\sum_{k=1}^{n-1}\binom{n}{k}k^{k-1}(n-k)^{n-k-1}.$
So far I've got that $T_{n}=n^{n-2}$ so it shows up in the LHS. For the sum it looks like $k^{k-1}$ is the number of labeled rooted trees on $k$ vertices and $(n-k)^{n-k-1}$ is the same thing on $n-k$ vertices and $\binom{n}{k}$ is picking which $k$ go in the first tree. Why would we multiply these two numbers and how does that equal the LHS? A hint would be very nice. Thanks.
HINT: Assume that $n\ge 2$, and let $T$ be a tree on $n$ vertices. There are $n-1$ ways to choose an edge $\{u,v\}$ of $T$ and two ways to paint the one of the vertices $u$ and $v$ red and the other blue, so there are $2(n-1)n^{n-2}$ trees on $n$ vertices with a distinguished edge whose ends are so painted.
Fix $k\in[n-1]$. There are $k\cdot k^{k-2}=k^{k-1}$ ways to pick a tree $T_1$ on $k$ vertices and choose a vertex $v_1$ to be painted red, and $(n-k)(n-k)^{n-k-2}=(n-k)^{n-k-1}$ ways to pick a tree $T_2$ on $n-k$ vertices and choose a vertex $v_2$ to be painted blue; adding an edge between $v_1$ and $v_2$ gives you a tree on $n$ decorated as in the first paragraph.