I posted an answer (which I have kept, below the horizontal rule) that starts out combinatorial and then becomes one of algebraic manipulation. This is, of course, disappointing: algebraic manipulation should code for combinatorics. No sooner did I click "submit" than I thought of a better answer.

Recall Cayley's formula that there are $n^{n-2}$ spanning trees on $n$ labeled nodes, and hence $n^n$ trees with labeled nodes, a particular node also marked $L$, and a particular node also marked $R$ (we can have $R=L$). To such a tree $\mathcal T$, do the following. Create a subset of the nodes $\mathcal L$ as follows: a node is in $\mathcal L$ if and only if its minimal path in the tree to $R$ passes through $L$. In particular, $L \in \mathcal L$, and we have $R \in \mathcal L$ iff $L=R$. Let $\mathcal R$ be the rest of the nodes, so that $\mathcal R$ is empty if $L=R$. Then the restriction of the tree $\mathcal T$ to the subset $\mathcal R$ gives a tree on $|\mathcal R|$ nodes with a marked vertex $R$, and the restriction of $\mathcal T$ to $\mathcal L$, provided it is not empty, gives a tree with two marked nodes ($L$ and the unique node in $\mathcal L$ that is adjacent to $R$).

Conversely, how can you construct a tree on a set of $n$ labeled nodes? One way is: first partition the set into two disjoint subsets $\mathcal L$ and $\mathcal R$, where $\mathcal L$ is not empty. Put on the set $\mathcal L$ a spanning tree, and also mark a node $L$. Provided $\mathcal R$ is not empty, put on it a spanning tree and mark two nodes ($R$ and $S$, say). Then build a spanning tree on the whole of $\mathcal L \cup \mathcal R$ by connecting $L$ to $S$. If $\mathcal R$ is empty, then take as your tree just $\mathcal L$, and let $R=L$.

For each $i = 1,\dots, n$, there are $\binom n i$ ways to pick $\mathcal L$ with $i = |\mathcal L|$. There are $i^{i-1}$ ways to put a tree on $\mathcal L$ and mark a node $L$. There are $(n-i)^{n-i}$ ways to put a tree on $\mathcal R$ and mark two nodes, if $n-i\neq 0$, and if $\mathcal R = \emptyset$, then there's $1 = 0^0$ thing to do. All together, we have: $$ n^n = \sum_{i=1}^n \binom n i i^{i-1} (n-i)^{n-i}$$ as each side counts the number of trees on $n$ labeled vertices with two marked nodes.

Recall Cayley's formula: the number of spanning trees on $n$ labeled nodes is $n^{n-2}$. For each tree, pick one of the $n-1$ edges, and pick an endpoint of it: you have just divided the nodes into two sets, neither of which is empty, and each of which has a distinguished vertex and a spanning tree.

Conversely, for each $j = 1,\dots,n-1$, there are $\binom n j$ ways to divide $n$ nodes into a pile of size $j$ and a pile of size $n-j$, and $j^{j-1}$ ways to put a spanning tree and pick a distinguished node from the first pile,and $(n-j)^{n-j}$ ways to pick a spanning tree and a distinguished node for the second pile.

All together, this proves: $$ 2(n-1)n^{n-2} = \sum_{j=1}^{n-1} \binom n j j^{j-1}(n-j)^{n-j-1} $$ Multiply the left-hand side by $n$ and the $j$th summand on the right-hand side by $j + (n-j)$: $$ \begin{aligned} 2(n-1)n^{n-1} & = \sum_{j=1}^{n-1} \binom n j j^{j-1}(n-j)^{n-j-1}\bigl(j + (n-j)\bigr) \\ & = \sum_{j=1}^{n-1}\binom n j j^{j}(n-j)^{n-j-1} + \sum_{j=1}^{n-1} \binom n j j^{j-1}(n-j)^{n-j} \\ &= 2\sum_{i=1}^{n-1}\binom n i i^{i-1}(n-i)^{n-i} \end{aligned} $$ where we recognize that the two sums in the middle line are the same, either $j\mapsto i$ or $j\mapsto n-i$.

Dividing by $2$ and adding $n^{n-1} = \binom n n n^{n-1} 0^0$ to both sides gives your formula.

I posted an answer (which I have kept, below the horizontal rule) that starts out combinatorial and then becomes one of algebraic manipulation. This is, of course, disappointing: algebraic manipulation should code for combinatorics. No sooner did I click "submit" than I thought of a better answer.

Recall Cayley's formula that there are $n^{n-2}$ spanning trees on $n$ labeled nodes, and hence $n^n$ trees with labeled nodes, a particular node also marked $L$, and a particular node also marked $R$ (we can have $R=L$). To such a tree $\mathcal T$, do the following. Create a subset of the nodes $\mathcal L$ as follows: a node is in $\mathcal L$ if and only if its minimal path in the tree to $R$ passes through $L$. In particular, $L \in \mathcal L$, and we have $R \in \mathcal L$ iff $L=R$. Let $\mathcal R$ be the rest of the nodes, so that $\mathcal R$ is empty if $L=R$. Then the restriction of the tree $\mathcal T$ to the subset $\mathcal L$ gives a tree on $|\mathcal L|$ nodes with a marked vertex $L$, and the restriction of $\mathcal T$ to $\mathcal R$, provided $\mathcal R$ is not empty, gives a tree with two marked nodes ($R$ and the unique node in $\mathcal R$ that is adjacent to $L\in \mathcal L$).

Conversely, how can you construct a tree on a set of $n$ labeled nodes? One way is: first partition the set into two disjoint subsets $\mathcal L$ and $\mathcal R$, where $\mathcal L$ is not empty. Put on the set $\mathcal L$ a spanning tree, and also mark a node $L$. Provided $\mathcal R$ is not empty, put on it a spanning tree and mark two nodes ($R$ and $S$, say). Then build a spanning tree on the whole of $\mathcal L \cup \mathcal R$ by connecting $L$ to $S$. If $\mathcal R$ is empty, then take as your tree just $\mathcal L$, and let $R=L$.

For each $i = 1,\dots, n$, there are $\binom n i$ ways to pick $\mathcal L$ with $i = |\mathcal L|$. There are $i^{i-1}$ ways to put a tree on $\mathcal L$ and mark a node $L$. There are $(n-i)^{n-i}$ ways to put a tree on $\mathcal R$ and mark two nodes, if $n-i\neq 0$, and if $\mathcal R = \emptyset$, then there's $1 = 0^0$ thing to do. All together, we have: $$ n^n = \sum_{i=1}^n \binom n i i^{i-1} (n-i)^{n-i}$$ as each side counts the number of trees on $n$ labeled vertices with two marked nodes.

Recall Cayley's formula: the number of spanning trees on $n$ labeled nodes is $n^{n-2}$. For each tree, pick one of the $n-1$ edges, and pick an endpoint of it: you have just divided the nodes into two sets, neither of which is empty, and each of which has a distinguished vertex and a spanning tree.

Conversely, for each $j = 1,\dots,n-1$, there are $\binom n j$ ways to divide $n$ nodes into a pile of size $j$ and a pile of size $n-j$, and $j^{j-1}$ ways to put a spanning tree and pick a distinguished node from the first pile,and $(n-j)^{n-j}$ ways to pick a spanning tree and a distinguished node for the second pile.

All together, this proves: $$ 2(n-1)n^{n-2} = \sum_{j=1}^{n-1} \binom n j j^{j-1}(n-j)^{n-j-1} $$ Multiply the left-hand side by $n$ and the $j$th summand on the right-hand side by $j + (n-j)$: $$ \begin{aligned} 2(n-1)n^{n-1} & = \sum_{j=1}^{n-1} \binom n j j^{j-1}(n-j)^{n-j-1}\bigl(j + (n-j)\bigr) \\ & = \sum_{j=1}^{n-1}\binom n j j^{j}(n-j)^{n-j-1} + \sum_{j=1}^{n-1} \binom n j j^{j-1}(n-j)^{n-j} \\ &= 2\sum_{i=1}^{n-1}\binom n i i^{i-1}(n-i)^{n-i} \end{aligned} $$ where we recognize that the two sums in the middle line are the same, either $j\mapsto i$ or $j\mapsto n-i$.

Dividing by $2$ and adding $n^{n-1} = \binom n n n^{n-1} 0^0$ to both sides gives your formula.

Recall Cayley's formula: the number of spanning trees on $n$ labeled nodes is $n^{n-2}$. For each tree, pick one of the $n-1$ edges, and pick an endpoint of it: you have just divided the nodes into two sets, neither of which is empty, and each of which has a distinguished vertex and a spanning tree.

Conversely, for each $j = 1,\dots,n-1$, there are $\binom n j$ ways to divide $n$ nodes into a pile of size $j$ and a pile of size $n-j$, and $j^{j-1}$ ways to put a spanning tree and pick a distinguished node from the first pile,and $(n-j)^{n-j}$ ways to pick a spanning tree and a distinguished node for the second pile.

All together, this proves: $$ 2(n-1)n^{n-2} = \sum_{j=1}^{n-1} \binom n j j^{j-1}(n-j)^{n-j-1} $$ Multiply the left-hand side by $n$ and the $j$th summand on the right-hand side by $j + (n-j)$: $$ \begin{aligned} 2(n-1)n^{n-1} & = \sum_{j=1}^{n-1} \binom n j j^{j-1}(n-j)^{n-j-1}\bigl(j + (n-j)\bigr) \\ & = \sum_{j=1}^{n-1}\binom n j j^{j}(n-j)^{n-j-1} + \sum_{j=1}^{n-1} \binom n j j^{j-1}(n-j)^{n-j} \\ &= 2\sum_{i=1}^{n-1}\binom n i i^{i-1}(n-i)^{n-i} \end{aligned} $$ where we recognize that the two sums in the middle line are the same, either $j\mapsto i$ or $j\mapsto n-i$.

Dividing by $2$ and adding $n^{n-1} = \binom n n n^{n-1} 0^0$ to both sides gives your formula.

I posted an answer (which I have kept, below the horizontal rule) that starts out combinatorial and then becomes one of algebraic manipulation. This is, of course, disappointing: algebraic manipulation should code for combinatorics. No sooner did I click "submit" than I thought of a better answer.

Recall Cayley's formula that there are $n^{n-2}$ spanning trees on $n$ labeled nodes, and hence $n^n$ trees with labeled nodes, a particular node also marked $L$, and a particular node also marked $R$ (we can have $R=L$). To such a tree $\mathcal T$, do the following. Create a subset of the nodes $\mathcal L$ as follows: a node is in $\mathcal L$ if and only if its minimal path in the tree to $R$ passes through $L$. In particular, $L \in \mathcal L$, and we have $R \in \mathcal L$ iff $L=R$. Let $\mathcal R$ be the rest of the nodes, so that $\mathcal R$ is empty if $L=R$. Then the restriction of the tree $\mathcal T$ to the subset $\mathcal R$ gives a tree on $|\mathcal R|$ nodes with a marked vertex $R$, and the restriction of $\mathcal T$ to $\mathcal L$, provided it is not empty, gives a tree with two marked nodes ($L$ and the unique node in $\mathcal L$ that is adjacent to $R$).

Conversely, how can you construct a tree on a set of $n$ labeled nodes? One way is: first partition the set into two disjoint subsets $\mathcal L$ and $\mathcal R$, where $\mathcal L$ is not empty. Put on the set $\mathcal L$ a spanning tree, and also mark a node $L$. Provided $\mathcal R$ is not empty, put on it a spanning tree and mark two nodes ($R$ and $S$, say). Then build a spanning tree on the whole of $\mathcal L \cup \mathcal R$ by connecting $L$ to $S$. If $\mathcal R$ is empty, then take as your tree just $\mathcal L$, and let $R=L$.

For each $i = 1,\dots, n$, there are $\binom n i$ ways to pick $\mathcal L$ with $i = |\mathcal L|$. There are $i^{i-1}$ ways to put a tree on $\mathcal L$ and mark a node $L$. There are $(n-i)^{n-i}$ ways to put a tree on $\mathcal R$ and mark two nodes, if $n-i\neq 0$, and if $\mathcal R = \emptyset$, then there's $1 = 0^0$ thing to do. All together, we have: $$ n^n = \sum_{i=1}^n \binom n i i^{i-1} (n-i)^{n-i}$$ as each side counts the number of trees on $n$ labeled vertices with two marked nodes.

Recall Cayley's formula: the number of spanning trees on $n$ labeled nodes is $n^{n-2}$. For each tree, pick one of the $n-1$ edges, and pick an endpoint of it: you have just divided the nodes into two sets, neither of which is empty, and each of which has a distinguished vertex and a spanning tree.

Conversely, for each $j = 1,\dots,n-1$, there are $\binom n j$ ways to divide $n$ nodes into a pile of size $j$ and a pile of size $n-j$, and $j^{j-1}$ ways to put a spanning tree and pick a distinguished node from the first pile,and $(n-j)^{n-j}$ ways to pick a spanning tree and a distinguished node for the second pile.

All together, this proves: $$ 2(n-1)n^{n-2} = \sum_{j=1}^{n-1} \binom n j j^{j-1}(n-j)^{n-j-1} $$ Multiply the left-hand side by $n$ and the $j$th summand on the right-hand side by $j + (n-j)$: $$ \begin{aligned} 2(n-1)n^{n-1} & = \sum_{j=1}^{n-1} \binom n j j^{j-1}(n-j)^{n-j-1}\bigl(j + (n-j)\bigr) \\ & = \sum_{j=1}^{n-1}\binom n j j^{j}(n-j)^{n-j-1} + \sum_{j=1}^{n-1} \binom n j j^{j-1}(n-j)^{n-j} \\ &= 2\sum_{i=1}^{n-1}\binom n i i^{i-1}(n-i)^{n-i} \end{aligned} $$ where we recognize that the two sums in the middle line are the same, either $j\mapsto i$ or $j\mapsto n-i$.

Dividing by $2$ and adding $n^{n-1} = \binom n n n^{n-1} 0^0$ to both sides gives your formula.